李傳江 吳國皎 程 成

（1.河南省地質(zhì)測繪總院，河南 鄭州 450007；2.河南省地質(zhì)礦產(chǎn)勘查開發(fā)局 第五地質(zhì)勘查院，河南 鄭州 450001）

進行空間索引的目的是為了在地理信息系統(tǒng)中對所選中的地理對象快速定位，以提升器空間操作速度以及效率。為此空間索引技術(shù)的質(zhì)量就直接的影響到GIS的整體性能。地理信息索引是通過地理要素的形狀、位置、地理對象之間的某種關(guān)系，將數(shù)據(jù)結(jié)構(gòu)按照一定的順序進行排列，這一過程包括三個部分，即地理對象的標(biāo)識、指向地理對象的指針以及外接矩形。常用的數(shù)據(jù)結(jié)構(gòu)有矢量結(jié)構(gòu)與柵格結(jié)構(gòu)，其中柵格數(shù)據(jù)是在連續(xù)鋪蓋的基礎(chǔ)上將連續(xù)空間離散化，也就是將整個連續(xù)空間覆蓋。而矢量法可看作是基于要素的方法，強調(diào)離散現(xiàn)象的存在。無論信息系統(tǒng)是一般關(guān)系型數(shù)據(jù)庫還是空間型數(shù)據(jù)庫，其根本任務(wù)就是進行信息檢索查詢。目前為止主要的空間索引方法有R樹系列、四叉樹、固定格網(wǎng)以及K-D-B樹等。

1 R樹系列空間索引

R樹系列從誕生以來經(jīng)過多年的發(fā)展已經(jīng)相繼出現(xiàn)了眾多的變形，例如R+樹、R3樹、Hibert R樹以及SR樹等一系列。同時以上變形均屬于一種平衡樹，其結(jié)構(gòu)也與B樹類似。R樹可以直接的實現(xiàn)對空間中占據(jù)一定范圍的地理要素進行索引，可以按照幾何對象的最小外接矩形MBR進行二維索引或者高維索引。R樹的每一個非葉結(jié)點均由若干MBR單元構(gòu)成，而MBR為包含有對應(yīng)的空間對象的最小矩形。

R樹最大的特點是兄弟結(jié)點所對應(yīng)的空間區(qū)域可以互相重疊，從而極大地方便了插入以及刪除操作，但是也使得空間搜索的效率大為降低。其原因在于空間中存在大量的重疊區(qū)域，為此需要經(jīng)過多條路徑的搜索才能得到結(jié)果。在這一基礎(chǔ)上人們經(jīng)過探索設(shè)計了R+樹，這一方法不存在重疊區(qū)域，極大地提升了空間搜索效率。但是由于在刪除以及插入之前要首先保證兄弟節(jié)點所對應(yīng)的的空間區(qū)域不能重疊，為此又降低了插入及刪除操作效率。

通過增加空間上鄰近的空間對象可以提升R樹的查詢效果，為此在組織R樹的時候可以有意識地讓空間對象的遠近體現(xiàn)在最近的共同祖先的遠近上。但是如何衡量空間對象的聚集成為一個較為復(fù)雜的問題，GutTman建議使用面積指標(biāo)來衡量空間上的聚集，也就是在進行插入操作中選擇插入新對象后MBR面積增長最小的結(jié)點為根的子樹。同樣在分裂溢出點時選擇各部分的最小包含矩形面積聚集最小結(jié)合方式的組合。R樹在進行插入操作中將葉結(jié)點與非葉結(jié)點分開考慮，同時分裂溢出點時的方法更為復(fù)雜。針對這一問題提出了Hilbert R樹，這一方法利用Hilbert曲線將多維空間對象映射到一維空間，同時利用變換來保持空間聚集的特性。

要實現(xiàn)R樹的組合機構(gòu)最優(yōu)化是一個復(fù)雜的過程，以上提出的改善方法雖然有所改進但依然不能令人滿意。例如不同的空間對象插入順序會得到不同結(jié)構(gòu)R樹，同時隨著空間對象的插入與刪除，最終得到的R樹的查詢效率的走向不可預(yù)知。

2 四叉樹空間索引機制

四叉樹索引是基于空間劃分組織索引的一種機制，通過將已知范圍空間劃分為四個等空間，如果需要還可以將其中一個或者幾個再次進行劃分，從而構(gòu)成了一個四叉樹劃分空間。

2.1 基于固定網(wǎng)格劃分的四叉樹索引

N層CELLQTREE所對應(yīng)的空間構(gòu)成一個2n×32n的網(wǎng)格，空間對象的ID信息存儲于每一個葉子結(jié)點中，如果同一父親的四個兄弟結(jié)點都要記錄統(tǒng)一ID對象，此時僅需將其記錄于該父親結(jié)點上，并按這一規(guī)定向上進行。CELLQTREE的構(gòu)成類似于網(wǎng)格索引，一個網(wǎng)格可以對應(yīng)多個網(wǎng)絡(luò)，但是有效地減少了節(jié)點的重復(fù)記錄。為此對于N=2的CELLQTREE空間劃分以及空間的插入、刪除步驟均較為簡單。由于不像R樹一樣要進行繁復(fù)的分裂與重新插入，為此具有較大的優(yōu)勢。此外這種索引方式的查詢也很簡單，例如當(dāng)需要檢測出某一個多邊形及其與之相較的空間對象時，通過CELLQTREE只需要檢測出多邊形所覆蓋的葉結(jié)點以及父親、祖先結(jié)點的多有空間對象，在此基礎(chǔ)上經(jīng)過相應(yīng)的空間運算就可以檢測出滿足空間要求的對象。CELLQTREE作為滿四叉樹并采用順序的數(shù)組存儲方式，為此其內(nèi)存耗費僅為鏈表結(jié)構(gòu)的四分之一，同時由于索引結(jié)構(gòu)可以放在內(nèi)存中，因而不會耗費I/O。

2.2 Super Map的線性可排序四叉樹空間索引

Super Map的線性可排序四叉樹空間索引較之前者有兩處不同，首先是結(jié)點編碼方式不同，其次是結(jié)點與空間對象的對應(yīng)關(guān)系不同。線性可排序的編碼方式首先是將四叉樹變?yōu)槎鏄洌缓蟀凑罩行虮闅v的順序?qū)Y(jié)點進行編碼。進行編碼查詢時要先根據(jù)查詢區(qū)域得到要搜索結(jié)點編號的集合，然后用SQL語句從表中檢測出符合要求的空間對象。但是這一方法不足之處在于面臨四叉樹結(jié)構(gòu)變化時，如果向下再劃分一層就需要給所有的結(jié)點進行重新編碼，從而降低了可排序性四叉樹的靈活性。

由此可見，四叉樹較之R樹有兩個優(yōu)勢：首先是插入以及刪除較為方便，耗時短；其次通過順序存儲線性表來表示索引降低了內(nèi)存需要。但是以空間劃分來組織索引面臨著這類索引的共同問題，即可調(diào)節(jié)性差。

3 結(jié)束語

從以上兩種索引方式的論述可見，四叉樹空間索引較之R樹具有較大的優(yōu)勢。首先查詢速度快，其次插入以及刪除方便；同時由于四叉樹是以空間劃分來組織索引結(jié)構(gòu)的索引機制，為此需要在索引之前指導(dǎo)空間對象所分布的范圍。但是R樹也有其獨特之處，例如通過數(shù)據(jù)組織索引使得索引具有很大靈活性，無需知道整個空間對象所在的范圍即可建立空間索引。

[1]陳述彭.魯學(xué)軍，周成虎.地理信息系統(tǒng)導(dǎo)論[M].北京：科學(xué)出版社，1999.

[2]蔡少華.GIS圖形空間關(guān)系的研究與實踐[D].鄭州：解放軍測繪學(xué)院，1998.

[3]龔健雅.GIS中矢量柵格一體化面向目標(biāo)數(shù)據(jù)模型的研究[D].武漢：武漢測繪科技大學(xué)，1991.