[發(fā)明專利]基于孩子節(jié)點(diǎn)的多粒度分布式讀寫鎖的R樹索引優(yōu)化方法

有效

• 申請?zhí)枺?/td>: 201811463042.3
• 申請日: 2018-12-03
• 公開（公告）號(hào): CN109582677B
• 公開（公告）日: 2021-05-04
• 發(fā)明（設(shè)計(jì)）人: 王波濤;李睿;田簫;黃明帥
• 申請（專利權(quán)）人: 東北大學(xué)
• 主分類號(hào): G06F16/22
• 分類號(hào): G06F16/22
• 代理公司: 大連理工大學(xué)專利中心 21200
• 代理人: 陳玲玉;梅洪玉

本發(fā)明提出了一種基于孩子節(jié)點(diǎn)的多粒度分布式讀寫鎖的R樹索引優(yōu)化方法，建立起了一個(gè)底層為網(wǎng)格索引，上層為R樹索引的雙層索引結(jié)構(gòu)；基于孩子節(jié)點(diǎn)建立了讀寫鎖，降低了鎖的粒度，支持較高的并行度，提高了查詢和更新等操作的執(zhí)行效率。此外，隨著查詢范圍的增大，以及移動(dòng)對(duì)象密度的增大，查詢的索引節(jié)點(diǎn)數(shù)目增多，也會(huì)導(dǎo)致查詢效率的降低。但整體效果優(yōu)于R樹根節(jié)點(diǎn)的分布式讀寫鎖。

技術(shù)領(lǐng)域

本發(fā)明涉及數(shù)據(jù)庫索引領(lǐng)域，具體的涉及一種基于孩子節(jié)點(diǎn)的多粒度分布式讀寫鎖的R樹索引優(yōu)化方法。

背景技術(shù)

基于位置服務(wù)(Location Based Service，LBS)為代表的移動(dòng)應(yīng)用已經(jīng)步入移動(dòng)大數(shù)據(jù)時(shí)代，成為人們?nèi)粘Ｉ畹闹匾M成部分，滴滴打車、高德地圖，日益方便著人們的生活，提高了人們的生活質(zhì)量。隨著移動(dòng)應(yīng)用規(guī)模的擴(kuò)大，移動(dòng)服務(wù)中的查詢也呈現(xiàn)鮮明的流式特征?，F(xiàn)有的系統(tǒng)無法有效地處理在擴(kuò)展性、實(shí)時(shí)性、可靠性及性能方面所面臨的挑戰(zhàn)。移動(dòng)大數(shù)據(jù)時(shí)代的數(shù)據(jù)處理不僅需要存儲(chǔ)與處理能力更強(qiáng)更靈活的計(jì)算平臺(tái)，還需要依托于計(jì)算平臺(tái)的相關(guān)移動(dòng)服務(wù)的處理與優(yōu)化技術(shù)。

在計(jì)算平臺(tái)的處理與優(yōu)化技術(shù)中，空間移動(dòng)對(duì)象數(shù)據(jù)庫起著重要的作用，它的核心功能旨在提供高效的查詢與更新處理，與高性能的索引結(jié)構(gòu)密切相關(guān)，因此，移動(dòng)對(duì)象的查詢處理和索引技術(shù)是移動(dòng)對(duì)象數(shù)據(jù)庫設(shè)計(jì)的核心部分。在多連續(xù)范圍查詢系統(tǒng)中，針對(duì)網(wǎng)格索引中空網(wǎng)格也要訪問造成額外開銷的問題，提出了基于HBase的支持頻繁更新的節(jié)點(diǎn)重組R樹的索引結(jié)構(gòu)。將空間區(qū)域映射在平面上，進(jìn)而劃分為網(wǎng)格，然后將包含有移動(dòng)對(duì)象的網(wǎng)格插入到R樹中。

針對(duì)這種雙層索引結(jié)構(gòu)，在移動(dòng)對(duì)象位置更新時(shí)，會(huì)出現(xiàn)性能以及讀寫鎖之間、寫鎖和寫鎖之間的沖突問題。為了解決讀寫鎖之間、寫鎖和寫鎖之間的沖突問題，采用Zookeeper分布式讀寫鎖在R樹根節(jié)點(diǎn)加鎖來解決多個(gè)進(jìn)程對(duì)共享資源的訪問。但是出現(xiàn)鎖的阻塞等待和并發(fā)度低的問題，尤其是在查詢和更新比較頻繁、以及R樹層級(jí)比較高的情況下。因?yàn)樵谑褂肦樹索引時(shí)，是對(duì)R樹根節(jié)點(diǎn)加鎖，獨(dú)占整個(gè)R樹，導(dǎo)致很多不受更新影響的節(jié)點(diǎn)也不可以并發(fā)訪問，降低了并行性，造成了很大的資源浪費(fèi)。如圖1所示，如果有一個(gè)查詢是對(duì)20號(hào)網(wǎng)格內(nèi)的數(shù)據(jù)，有一個(gè)更新是對(duì)63號(hào)網(wǎng)格內(nèi)的數(shù)據(jù)，兩個(gè)區(qū)域并不相交，在進(jìn)行查詢操作時(shí)，更新操作等待根鎖，由此會(huì)造成資源利用率低下。

發(fā)明內(nèi)容

本發(fā)明提供一種基于孩子節(jié)點(diǎn)的多粒度分布式讀寫鎖的R樹索引優(yōu)化方法。在R樹索引構(gòu)建穩(wěn)定后，根節(jié)點(diǎn)就很難再分裂，基于此特點(diǎn)，本發(fā)明設(shè)置根節(jié)點(diǎn)容量和MBR的參數(shù)值，使其不再分裂，將鎖加在孩子節(jié)點(diǎn)，既避免了多個(gè)操作并發(fā)等待鎖，也保證了查詢結(jié)果的正確性。解決了現(xiàn)有技術(shù)的不足。

本發(fā)明采用的技術(shù)方案：

一種基于孩子節(jié)點(diǎn)的多粒度分布式讀寫鎖的R樹索引優(yōu)化方法，包括如下步驟：

步驟一，首先將整個(gè)空間區(qū)域進(jìn)行規(guī)則劃分，劃分成大小相同的網(wǎng)格，將移動(dòng)對(duì)象存儲(chǔ)到網(wǎng)格的索引項(xiàng)里，建立起一個(gè)底層的網(wǎng)格索引；然后，用R樹索引網(wǎng)格，R樹的葉子節(jié)點(diǎn)存儲(chǔ)網(wǎng)格的ID；這樣，就建立起了一個(gè)底層為網(wǎng)格索引，上層為R樹索引的雙層索引結(jié)構(gòu)，如圖3所示。調(diào)用R樹程序獲取范圍查詢內(nèi)的網(wǎng)格，實(shí)現(xiàn)范圍查詢的加讀鎖過程；如果R樹root節(jié)點(diǎn)有孩子節(jié)點(diǎn)并且root節(jié)點(diǎn)的MBR與查詢范圍相交，則繼續(xù)獲取與查詢范圍相交的孩子節(jié)點(diǎn)；然后對(duì)該孩子節(jié)點(diǎn)加讀鎖；逐層查找R樹各層節(jié)點(diǎn)直至葉子節(jié)點(diǎn)；如果葉子節(jié)點(diǎn)的MBR與查詢范圍相交，則返回葉子節(jié)點(diǎn)的結(jié)果集合，否則就釋放上述孩子節(jié)點(diǎn)的讀鎖；

步驟二，移動(dòng)對(duì)象的位置更新過程中，在孩子節(jié)點(diǎn)加寫鎖，包括兩個(gè)部分：

第一部分：在R樹索引中插入節(jié)點(diǎn)時(shí)加寫鎖過程；

在R樹索引中插入網(wǎng)格，首先計(jì)算出網(wǎng)格左下角坐標(biāo)和右上角坐標(biāo)；然后初始化R樹root節(jié)點(diǎn)重要參數(shù)：MBR和節(jié)點(diǎn)容量；獲取實(shí)例root節(jié)點(diǎn)，從root節(jié)點(diǎn)開始向下遍歷找到與該網(wǎng)格相交的孩子節(jié)點(diǎn)；對(duì)孩子節(jié)點(diǎn)加寫鎖；逐層查找直到應(yīng)該將該網(wǎng)格插入其中的葉子節(jié)點(diǎn)；對(duì)孩子節(jié)點(diǎn)釋放寫鎖；