詳述幾種常用的柵格數(shù)據(jù)的空間索引方法

李傳江 吳國皎 程 成

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

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

1 R樹系列空間索引

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

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

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

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

2 四叉樹空間索引機制

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

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

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

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

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

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

3 結束語

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

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

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

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