基于改進四叉樹的地理實體快速查詢算法

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

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

基于改進四叉樹的地理實體快速查詢算法

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

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

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

四叉樹；地理實體；空間查詢

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

1 四叉樹索引

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

1.1 地理實體的最小外包矩形

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

圖1 四叉樹分割和地理實體要素的節(jié)點分配

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

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

1）在改進四叉樹中，判斷一個地理實體位于第i（i =0,1,2,…,n-1，i

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

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

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

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

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

2 空間查詢算法的實現(xiàn)

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

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

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

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

2.1.2 索引文件的生成

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

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

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

2.2 地理實體查詢算法

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

2.2.1 點查詢

點查詢具體步驟為：

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

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

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

2.2.2 開窗查詢

算法描述如下：

開窗查詢的具體實現(xiàn)步驟為：

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

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

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

3 實驗設(shè)計與結(jié)果分析

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

實驗采用多個數(shù)據(jù)集，不同數(shù)據(jù)集分別代表了不同的地理實體類型和數(shù)據(jù)量。詳細的數(shù)據(jù)集信息見表1。

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

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

3.2 實驗結(jié)果分析

3.2.1 CPU時間

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

表2 CPU時間/ms

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

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

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

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

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

4 結(jié) 語

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

[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ù)庫索引技術(shù)[M]．上海:上海交通大學出版社,2006

[3] 郭仁忠．空間分析[M]．武漢:武漢測繪科技大學出版社,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]．測繪科學,2009,34(1):60-62,68

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

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

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

P208

B

1672-4623（2017）01-0032-04

10.3969/j.issn.1672-4623.2017.01.010

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

2015-11-24。

項目來源：國家自然科學基金資助項目（41501507）。