詳述幾種常用的柵格數據的空間索引方法

李傳江 吳國皎 程 成

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

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

1 R樹系列空間索引

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

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

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

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

2 四叉樹空間索引機制

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

2.1 基于固定網格劃分的四叉樹索引

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

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

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

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

3 結束語

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

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

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

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