彭召軍，王青山，熊 偉，李柏地

（1.信息工程大學(xué)，河南 鄭州 450001；2.78138部隊(duì)，四川 成都 610000）

基于改進(jìn)四叉樹(shù)的地理實(shí)體快速查詢(xún)算法

彭召軍1，王青山1，熊 偉1，李柏地2

（1.信息工程大學(xué)，河南 鄭州 450001；2.78138部隊(duì)，四川 成都 610000）

通過(guò)改進(jìn)傳統(tǒng)四叉樹(shù)的數(shù)據(jù)組織和節(jié)點(diǎn)分配，將被索引的地理實(shí)體要素合理地分配到樹(shù)中對(duì)應(yīng)的節(jié)點(diǎn)中，減少了數(shù)據(jù)冗余，節(jié)點(diǎn)的分布也更為合理。以地理實(shí)體數(shù)據(jù)為例，綜合比較了不同數(shù)據(jù)集在建立索引前后空間查詢(xún)效率上的差異。結(jié)果表明，該算法具有較高的查詢(xún)性能和實(shí)用價(jià)值。

四叉樹(shù)；地理實(shí)體；空間查詢(xún)

空間索引是指在存儲(chǔ)空間數(shù)據(jù)時(shí)，依據(jù)空間對(duì)象的位置、形狀或空間對(duì)象之間的某種空間關(guān)系，按一定順序排列的一種數(shù)據(jù)結(jié)構(gòu)，其中包含空間對(duì)象的概要信息，如對(duì)象的標(biāo)識(shí)、外接矩形以及指向空間對(duì)象實(shí)體的指針[1]。傳統(tǒng)的數(shù)據(jù)庫(kù)索引技術(shù)主要有B-樹(shù)、B+-樹(shù)、二叉樹(shù)、ISAM索引和哈希索引等[2]，這些技術(shù)都是針對(duì)一維屬性數(shù)據(jù)設(shè)計(jì)的，不能直接用于空間數(shù)據(jù)庫(kù)的索引。針對(duì)多維空間數(shù)據(jù)具有的空間關(guān)系復(fù)雜、數(shù)據(jù)量大、數(shù)據(jù)表達(dá)困難[3]等特點(diǎn)，本文在傳統(tǒng)四叉樹(shù)的基礎(chǔ)上，通過(guò)改進(jìn)其空間分割、節(jié)點(diǎn)分配及數(shù)據(jù)組織方式，設(shè)計(jì)了一種基于改進(jìn)四叉樹(shù)的地理實(shí)體快速查詢(xún)算法；并利用真實(shí)地理實(shí)體數(shù)據(jù)，對(duì)算法進(jìn)行了測(cè)評(píng)，取得了良好的效果。

1 四叉樹(shù)索引

四叉樹(shù)索引是一種面向主存的空間索引技術(shù)，是建立在對(duì)區(qū)域循環(huán)分解原則之上的一種層次數(shù)據(jù)結(jié)構(gòu)，在計(jì)算機(jī)圖形處理、圖像處理及GIS中有廣泛的應(yīng)用?？臻g四叉樹(shù)算法是一種空間均勻網(wǎng)格剖分算法，其將包含整個(gè)場(chǎng)景的空間按x、y方向分割成4個(gè)子方塊網(wǎng)格，從而組成一棵四叉樹(shù)。若某一子方塊網(wǎng)格中所包含的要素?cái)?shù)量大于給定的閾值，則對(duì)該子方塊作進(jìn)一步遞歸分割，直到四叉樹(shù)的每一個(gè)葉子節(jié)點(diǎn)的子方塊所含要素?cái)?shù)量均小于給定的閾值為止[4-5]。

1.1 地理實(shí)體的最小外包矩形

在實(shí)際應(yīng)用中，最小外包矩形能夠很好地描述地理實(shí)體的屬性特征。如圖1所示，以線狀要素和面狀要素為例，通過(guò)建立要素的最小外包矩形，確定各要素在四叉樹(shù)中的層次，再依據(jù)最小外包矩形的范圍將各要素分配到四叉樹(shù)相應(yīng)的節(jié)點(diǎn)中去。

圖1 四叉樹(shù)分割和地理實(shí)體要素的節(jié)點(diǎn)分配

1.2 改進(jìn)四叉樹(shù)的數(shù)據(jù)結(jié)構(gòu)

如圖2、3所示，傳統(tǒng)四叉樹(shù)和改進(jìn)四叉樹(shù)的主要區(qū)別為：

1）在改進(jìn)四叉樹(shù)中，判斷一個(gè)地理實(shí)體位于第i（i =0,1,2,…,n-1，i

2）在改進(jìn)四叉樹(shù)中，節(jié)點(diǎn)的分裂完全按照地理實(shí)體要素的數(shù)據(jù)分布特點(diǎn)而定，分裂后得到4個(gè)相等子節(jié)點(diǎn)矩形，根節(jié)點(diǎn)或某些中間節(jié)點(diǎn)可能不包含對(duì)象，某些節(jié)點(diǎn)可能包含多個(gè)對(duì)象。只要對(duì)象的最小外包矩形滿(mǎn)足1）中的條件，對(duì)象就會(huì)被準(zhǔn)確地分配到四叉樹(shù)對(duì)應(yīng)的層級(jí)中，四叉樹(shù)的節(jié)點(diǎn)也分裂到對(duì)應(yīng)的層級(jí)。

3）在改進(jìn)四叉樹(shù)中，為了控制樹(shù)的深度，根據(jù)地理實(shí)體數(shù)據(jù)的特點(diǎn)，系統(tǒng)動(dòng)態(tài)設(shè)置一個(gè)分裂的最大深度MaxDepth。當(dāng)四叉樹(shù)的層級(jí)達(dá)到MaxDepth時(shí)，四叉樹(shù)節(jié)點(diǎn)不再繼續(xù)向下分裂，而是將此地理實(shí)體要素加入到四叉樹(shù)中層級(jí)為MaxDepth所對(duì)應(yīng)的父親節(jié)點(diǎn)中。

4）對(duì)于某一地理數(shù)據(jù)集，在改進(jìn)四叉樹(shù)索引中，設(shè)置一個(gè)節(jié)點(diǎn)的最小度MinDegree。對(duì)一棵已經(jīng)建立好的四叉樹(shù)進(jìn)行“節(jié)點(diǎn)最小度”處理，如果四叉樹(shù)節(jié)點(diǎn)中存儲(chǔ)的地理實(shí)體要素個(gè)數(shù)小于MinDegree，則將此節(jié)點(diǎn)中的要素添加到此節(jié)點(diǎn)的父親節(jié)點(diǎn)中去，再將此節(jié)點(diǎn)設(shè)為空。

圖2 傳統(tǒng)四叉樹(shù)的數(shù)據(jù)結(jié)構(gòu)（以線狀要素為例，N為層數(shù)）

圖3 改進(jìn)四叉樹(shù)的數(shù)據(jù)結(jié)構(gòu)（以線狀要素為例，N為層數(shù)）

2 空間查詢(xún)算法的實(shí)現(xiàn)

2.1 四叉樹(shù)索引的構(gòu)建

2.1.1 索引樹(shù)的創(chuàng)建

在改進(jìn)四叉樹(shù)中，需要記錄的屬性有：地理實(shí)體要素的FeatureID（int型）、層次信息Level（int型）、最小外包矩形的左上角點(diǎn)（L_x, L_y）和右下角點(diǎn)（R_x, R_y）坐標(biāo)（double型）、父親節(jié)點(diǎn)指針Parent和4個(gè)孩子指針Child[4]。四叉樹(shù)的結(jié)構(gòu)定義如下：

四叉樹(shù)索引的構(gòu)建過(guò)程為：①確定樹(shù)的根節(jié)點(diǎn)[6]。首先分別確定各地理實(shí)體要素(點(diǎn)、線、面)的最小外包矩形，并對(duì)各要素的最小外包矩形的左上角點(diǎn)和右下角點(diǎn)坐標(biāo)加以比較，得到能夠涵蓋所有要素的最小外包矩形：rootBound(min(Left_Xi,Left_Yi, Right_Xi,Right_Yi))。②確定地理實(shí)體要素在四叉樹(shù)中的層級(jí)（Level< MaxDepth），找到需要插入的子節(jié)點(diǎn)，條件如§1．2中所述。③將地理實(shí)體要素插入到對(duì)應(yīng)的子節(jié)點(diǎn)中，重復(fù)上述步驟直至所有的要素插入完畢。④對(duì)建立好的四叉樹(shù)作“節(jié)點(diǎn)最小度”處理，使每個(gè)節(jié)點(diǎn)的要素?cái)?shù)量都大于MinDegree。插入算法代碼為：

2.1.2 索引文件的生成

基于二進(jìn)制文件在數(shù)據(jù)讀寫(xiě)方面的優(yōu)勢(shì)，將四叉樹(shù)索引寫(xiě)入二進(jìn)制文件中，生成包含地理實(shí)體要素關(guān)鍵屬性的四叉樹(shù)索引文件，具體流程如圖4所示。

圖4 地理實(shí)體數(shù)據(jù)處理流程圖

按照四叉樹(shù)的編碼特性和數(shù)據(jù)組織方式[7]，采取深度遍歷的方式，將要素的nID、nPosition、MBR按順序?qū)懭胨饕龜?shù)據(jù)文件。相比于原始數(shù)據(jù)，新生成的索引數(shù)據(jù)占用空間更少，讀取效率更高。在執(zhí)行查詢(xún)、插入、刪除、更新等空間操作時(shí)，算法只需在初次執(zhí)行操作時(shí)構(gòu)建四叉樹(shù)索引，以后僅裝載包含四叉樹(shù)索引的地理實(shí)體數(shù)據(jù)文件即可。依據(jù)四叉樹(shù)索引的空間剖分原則和數(shù)據(jù)組織方式，讀取數(shù)據(jù)時(shí)，可根據(jù)根節(jié)點(diǎn)的最小外包矩形的范圍確定各層級(jí)子節(jié)點(diǎn)的最小外包矩形，依次讀取各節(jié)點(diǎn)的數(shù)據(jù)，并把整個(gè)索引樹(shù)快速還原，避免了頻繁讀取原始數(shù)據(jù)和重復(fù)構(gòu)建四叉樹(shù)索引而造成的浪費(fèi)，提高了空間操作的效率。

2.2 地理實(shí)體查詢(xún)算法

點(diǎn)查詢(xún)和開(kāi)窗查詢(xún)是GIS中兩類(lèi)重要的空間查詢(xún)方式。點(diǎn)查詢(xún)是查找距離鼠標(biāo)點(diǎn)一定閾值范圍內(nèi)的所有地理實(shí)體對(duì)象；開(kāi)窗查詢(xún)是查找在給定的區(qū)域范圍內(nèi)的所有要素對(duì)象（點(diǎn)、線、面），常見(jiàn)的開(kāi)窗查詢(xún)有按矩形、圓、多邊形查詢(xún)[8]。

2.2.1 點(diǎn)查詢(xún)

點(diǎn)查詢(xún)具體步驟為：

1）從四叉樹(shù)的根節(jié)點(diǎn)開(kāi)始，逐節(jié)點(diǎn)遞歸查詢(xún)，若節(jié)點(diǎn)的最小外包矩形與給定閾值范圍相交，記錄節(jié)點(diǎn)中所有地理實(shí)體對(duì)象的ID；若節(jié)點(diǎn)不是葉子節(jié)點(diǎn)，以子節(jié)點(diǎn)為參數(shù)繼續(xù)執(zhí)行此過(guò)程，直到是葉子節(jié)點(diǎn)為止。

2）將搜索完畢后得到的所有記錄存入一個(gè)整型數(shù)組中，按照ID大小進(jìn)行排序，這將更加有利于從索引文件中按ID號(hào)快速提取相應(yīng)的地理實(shí)體對(duì)象。

3）對(duì)數(shù)組中所有ID對(duì)應(yīng)的地理實(shí)體對(duì)象遍歷搜索，判斷查詢(xún)點(diǎn)的閾值范圍是否與對(duì)象的外包矩形相交。若相交，說(shuō)明查找成功，否則將此ID從數(shù)組中刪除。

2.2.2 開(kāi)窗查詢(xún)

算法描述如下：

開(kāi)窗查詢(xún)的具體實(shí)現(xiàn)步驟為：

1）從根節(jié)點(diǎn)開(kāi)始，逐節(jié)點(diǎn)遞歸搜索。若節(jié)點(diǎn)的最小外包矩形與查詢(xún)區(qū)域相交，表明查詢(xún)區(qū)域內(nèi)可能包含對(duì)象，繼續(xù)遞歸搜索直至步驟2）條件成立。

2）若查詢(xún)區(qū)域包含某一節(jié)點(diǎn)中的某些對(duì)象（對(duì)象可能不唯一）的最小外包矩形，將這些對(duì)象添加到結(jié)果容器中，繼續(xù)遞歸搜索直至葉子節(jié)點(diǎn)。容器中所含的對(duì)象即為開(kāi)窗查詢(xún)的最終結(jié)果。

需要說(shuō)明的是，點(diǎn)查詢(xún)和開(kāi)窗查詢(xún)只能對(duì)海量實(shí)體對(duì)象進(jìn)行初步過(guò)濾，要想得到精確的結(jié)果，還需對(duì)結(jié)果進(jìn)行精確查詢(xún)判斷。通過(guò)構(gòu)建四叉樹(shù)索引，排除了大量與查詢(xún)條件無(wú)關(guān)的地理實(shí)體對(duì)象，極大地提高了整個(gè)空間查詢(xún)的效率。

3 實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析

3.1 實(shí)驗(yàn)內(nèi)容與設(shè)置

實(shí)驗(yàn)采用多個(gè)數(shù)據(jù)集，不同數(shù)據(jù)集分別代表了不同的地理實(shí)體類(lèi)型和數(shù)據(jù)量。詳細(xì)的數(shù)據(jù)集信息見(jiàn)表1。

表1 數(shù)據(jù)集信息

算法采用C++編程語(yǔ)言實(shí)現(xiàn)，對(duì)測(cè)試數(shù)據(jù)集建立改進(jìn)四叉樹(shù)索引（MaxDegree=20，MaxDepth=10）。為了驗(yàn)證算法的性能，本文將建立了四叉樹(shù)索引與未建立索引的地理實(shí)體數(shù)據(jù)集的查詢(xún)性能進(jìn)行比較，衡量算法性能的指標(biāo)包括CPU時(shí)間和磁盤(pán)I/O次數(shù)。

3.2 實(shí)驗(yàn)結(jié)果分析

3.2.1 CPU時(shí)間

表2為建立了四叉樹(shù)索引的地理實(shí)體數(shù)據(jù)集和未建立索引的地理實(shí)體數(shù)據(jù)集執(zhí)行查詢(xún)操作的CPU時(shí)間開(kāi)銷(xiāo)。表中包含了4個(gè)數(shù)據(jù)集轉(zhuǎn)換成二進(jìn)制文件和建立四叉樹(shù)索引之后的索引文件大小、建立四叉樹(shù)索引的CPU時(shí)間開(kāi)銷(xiāo)以及執(zhí)行查詢(xún)操作時(shí)的CPU時(shí)間開(kāi)銷(xiāo)。

表2 CPU時(shí)間/ms

1）無(wú)論是否建立索引，查詢(xún)時(shí)間都隨數(shù)據(jù)量的增大而不斷增加。執(zhí)行查詢(xún)操作時(shí)，構(gòu)建四叉樹(shù)索引的過(guò)程所需CPU時(shí)間消耗較大；但當(dāng)索引構(gòu)建完成后，查詢(xún)時(shí)間與未建立索引的查詢(xún)時(shí)間相差了幾百倍，查詢(xún)效率明顯提高?？梢哉f(shuō)，建立四叉樹(shù)索引的數(shù)據(jù)集執(zhí)行查詢(xún)操作的CPU時(shí)間幾乎全用在了構(gòu)建索引的過(guò)程中。

2）隨著數(shù)據(jù)量的不斷增加，未建立索引的數(shù)據(jù)集在執(zhí)行查詢(xún)操作時(shí)的CPU時(shí)間消耗急劇增加。這是因?yàn)槲唇⑺饕?，?shù)據(jù)缺乏有效組織，查詢(xún)操作采取的方式為簡(jiǎn)單的順序遍歷，而這種方式在數(shù)據(jù)量增多時(shí)存在固有缺陷。建立索引的數(shù)據(jù)集執(zhí)行單次查詢(xún)操作的CPU時(shí)間消耗隨數(shù)據(jù)量的增加無(wú)明顯變化。

3.2.2 磁盤(pán)I/O次數(shù)

圖5顯示了4個(gè)數(shù)據(jù)集執(zhí)行查詢(xún)操作時(shí)的磁盤(pán)I/O次數(shù)。與CPU時(shí)間消耗類(lèi)似，隨著數(shù)據(jù)量的增加，構(gòu)建四叉樹(shù)索引所花費(fèi)的磁盤(pán)I/O次數(shù)顯著增加。構(gòu)建索引時(shí)，數(shù)據(jù)的讀取和寫(xiě)入、索引文件的生成及四叉樹(shù)構(gòu)建時(shí)的遞歸插入等操作所需要的磁盤(pán)I/O次數(shù)遠(yuǎn)大于不建立索引時(shí)所需的磁盤(pán)I/O次數(shù)。單就查詢(xún)操作的實(shí)現(xiàn)而言，建立四叉樹(shù)索引和未建立索引所需要的磁盤(pán)I/O次數(shù)相差并不明顯。

圖5 4種數(shù)據(jù)集的磁盤(pán)I/O

4 結(jié) 語(yǔ)

本文提出了一種基于改進(jìn)四叉樹(shù)的地理實(shí)體要素快速查詢(xún)算法，在實(shí)體數(shù)據(jù)集的查詢(xún)操作中嵌入改進(jìn)的四叉樹(shù)索引，提高了數(shù)據(jù)查詢(xún)與檢索的效率，算法取得了良好的效果。但本算法也存在不足，在數(shù)據(jù)量或地形形態(tài)相差較大時(shí)，四叉樹(shù)分割閾值的選取、深度的動(dòng)態(tài)控制以及四叉樹(shù)的平衡性對(duì)最終的查詢(xún)結(jié)果和查詢(xún)效率影響很大，需要對(duì)多種實(shí)驗(yàn)結(jié)果進(jìn)行綜合分析后選取合適的閾值，這是下一步需要研究解決的問(wèn)題。

[1] GUO J,ZHOU D R,GUO W, et al． Research of Indexing Techniques for Spatial Databases[J]． Application Research of Computers,2003,20(12):12-14

[2] 郭薇,郭菁,胡志勇．空間數(shù)據(jù)庫(kù)索引技術(shù)[M]．上海:上海交通大學(xué)出版社,2006

[3] 郭仁忠．空間分析[M]．武漢:武漢測(cè)繪科技大學(xué)出版社,2000

[4] WANG T,LIU J P,WU H H． The Extraction of Contour Lines from Grid DEM Based on Sorting[J]． Acta Geodaetica Et Cartographica Sinica,2006,35(4):392-394

[5] 夏宇,朱欣焰．高維空間數(shù)據(jù)索引技術(shù)研究[J]．測(cè)繪科學(xué),2009,34(1):60-62,68

[6] 盧蓉,范勇,陳念年,等．一種提取標(biāo)圖像最小外接矩形的快速算法[J],計(jì)算機(jī)工程,2010,36(21):178-180

[7] 李建勛,沈冰,姜仁貴,等．面向影像金字塔的四叉樹(shù)空間索引算法[J]．計(jì)算機(jī)工程,2011,37(10):11-13

[8] 董鵬, 楊崇俊, 芮小平, 等．一種基于改進(jìn)四叉樹(shù)的GIS空間選擇查詢(xún)算法:以ESRI shape格式文件為例[J]．計(jì)算機(jī)工程與應(yīng)用,2003,39(13):58-61

P208

B

1672-4623（2017）01-0032-04

10.3969/j.issn.1672-4623.2017.01.010

彭召軍，碩士研究生，主要從事地理空間數(shù)據(jù)庫(kù)索引等方面的研究工作。

2015-11-24。

項(xiàng)目來(lái)源：國(guó)家自然科學(xué)基金資助項(xiàng)目（41501507）。