動態廣義表空間索引方法

何 珍 文，鄭 祖 芳，劉 剛，吳 沖 龍

動態廣義表空間索引方法

何 珍 文，鄭 祖 芳，劉 剛，吳 沖 龍

（中國地質大學（武漢）計算機學院，湖北 武漢 430074）

提出了一種新的動態空間索引結構X-Lists，設計實現了X-Lists的動態插入、動態刪除、查找等算法，并進行了算法實驗。X-Lists是一種支持高維點查詢和區域查詢的廣義表，實驗表明，X-Lists在索引構建與區域查找方面性能明顯優于現有R-Tree及其改進索引結構。

空間索引;R樹;廣義表;X-Lists

0 引言

高效的多維空間索引是海量多維空間數據存儲管理與有效調度的基礎。由于空間數據的海量性及空間查詢的高度復雜性，如何建立高效的多維空間索引實現海量空間數據的快速調度一直是人們研究的重點與難點問題之一。近30年眾多學者提出了多種空間索引方法［1－3］，大致可分為線性索引、網格索引和樹形索引三大類（圖1），但目前研究使用最廣泛的三維空間索引依然是R樹系列索引方法。

線性索引是一種最直觀簡單的索引，但在大型空間數據庫中訪問效率較低，較少被采用。網格索引是將研究區域縱橫分成若干個均等的小塊，每小塊都作為一個桶，將落在該小塊內的地物對象放入該小塊對應的桶中。當用戶進行查詢時，首先計算出用戶查詢對象所在格網，然后在該網格中快速查詢所選空間實體。目前在3DGIS中常被用作一級索引與R樹系列索引混合使用［3］。目前絕大部分的空間索引都是樹形索引（圖1），并且高維索引大都基于R-Tree［4］。R-Tree奠定了高維空間索引的技術架構［5］，是目前應用最為廣泛的一種空間索引結構，許多商用空間數據庫系統（如Oracle Spatial、IBM DB2 Spatial DataBlade、MySQL Spatial Extensions和MapInfo Spatial Ware等）均提供對R-Tree的支持，開放源碼系統PostgreSQL也實現了R-Tree。近20多年來，許多學者致力于R-Tree的研究，在R-Tree的基礎上衍生出了許多變種，比較典型的有R＋－Tree［6］、R＊-Tree［7］、壓 縮 R-Tree［8］、Hilbert RTree［9］、ER＊－Tree［10］、CSR－Tree［1，2］等。

圖1 空間索引方法分類［3］Fig.1 Classification of spatial index method

目前大量使用和研究的多維空間索引依然是以R-Tree及其衍生索引結構為主。廣義表是一種非線性數據結構，是線性表和樹的推廣，被廣泛應用于多項式處理、DNA計算機、表處理語言LISP、人工智能等領域。2010年，筆者對基于廣義表的三維空間索引進行了研究，提出了R-Lists［11］空間索引結構，其邊界矩形采用三維矩形，沒有給出該結構實現的具體輔助算法。

本文以R-Lists為基礎，對基于廣義表的動態空間索引結構進行了研究，提出了一種新的動態索引結構X-Lists，設計實現了X-Lists的動態插入、動態刪除、查找等算法，并進行了算法實驗。研究表明：在內存空間占用方面，X-Lists的構建性能明顯優于R-Tree和CSR-Tree;在索引構建時間方面，X-Lists與 R-Tree相 當，優 于 R＊-Tree和 CSR-Tree;XLists的查詢性能在時間和空間占用上均明顯優于R-Tree和CSR-Tree;X-Lists能有效地支持高維點查詢和區域查詢，具有廣義表的一般屬性及其優良性質，在具有高效的空間索引性能的同時，將更有利于對大規模空間數據集進行空間關系推理，或將為基于索引結構的空間關系的智能推理提供新的實現思路和方法。

1 X-Lists索引結構

廣義表一般記為：

其中：GL（Generalized List）是廣義表名稱，n是其長度，ei是GL的一個元素，可以是原子（Atom）或子表（Sublist），這就決定了廣義表的遞歸結構。X-Lists是一種帶有最小包圍邊界并限定了表長度的廣義表。這里的X代表單個或多個空間對象的任意形狀的可進行疊置（Overlap）運算的最小包圍體，常用的是超維最小邊界矩形（MRB）、超球體或超維凸包體等。在高維點查詢中一般采用超球體具有較高效率，在區域查詢中一般采用多維最小邊界矩形。在本文的算法實現中，如果沒有特殊說明，最小包圍體用最小邊界矩形（MRB）表示。

在X-Lists中，每個原子元素對應一個空間對象SOj，記為：

其中：X＝（X0，X1，…，Xd－1）是一個d維最小包圍體，d是空間維度;SO＿Identifier代表空間數據庫中空間對象的唯一標識，在實現過程中一般采用空間對象ID或指針表示。對于X-Lists的子表，則對應一個約束在一定空間范圍的空間對象集合或者集合的集合，記為：

如果X代表矩形，以 Guttman［4］給出的R-Tree的示例數據為例，且令m＝3，則采用X-Lists表示廣義表XL為：

采用擴展線性存儲方式，XL的存儲結構如圖2所示，標有數字的為原子，標有圓圈的為子表。

圖2 Guttman示例數據對應的X-ListsFig.2 X-Lists for Guttman′s sample data

為了便于查找與更新實現，本文對擴展線性存儲方式采用了雙向鏈表形式，如果需要節省空間，也可以采用單向鏈表實現。后面的相關算法采用的是雙向鏈表的實現方式。采用雙向鏈表的擴展線性存儲方式，X-Lists中的節點元素用C?語言描述如下：

其中：模板參數MBXVALUETYPE表示包圍盒的分量類型，一般為float或double型;NUMDIMS表示空間維數;OBJTYPE表示空間對象或其唯一標識類型，當X-Lists用于文件系統時，OBJTYPE是一個帶有文件指針和偏移位置信息的結構體，為闡述方便，本文將其定義為int型;Element的prev和next成員變量用于雙向鏈表指針;type表示元素類型，如果為0表示原子，為1表示子表;當類型為原子元素時，obj用于唯一標識空間對象;當類型為子表時，sublist指向子表的頭節點;bound表示子表或原子的最小包圍邊界，可以是超矩形或超球體等，本文采用對象Bound Box實現，只要實現了Bound Box的overlap、union等相關虛函數的幾何實體都可以在X-Lists中使用，提高了X-Lists的可擴展性。

2 查找與更新算法

查找與更新算法是索引的核心算法，其效率直接決定索引的性能好壞。本文重點討論X-Lists索引結構的查找、動態插入、動態刪除等算法。假定空間對象的 MBX的集合為R＝｛Ri｜i∈［0，n］｝，當前待處理的 X-Lists為CXL＝｛C0，C1，…，Cj，…，Ck｝，其中0≤j≤k，且k＜m。

2.1 查找算法

查找算法（Searching）即在X-Lists中查找符合給定條件的原子元素。最常用的查詢是空間范圍查詢，也即給定一個待查詢的MBX值S，查詢X-Lists中有哪些原子元素落在MBX中。設CXL的頭指針為H，由于X-Lists是一種遞歸結構，因此，查找算法可以采用遞歸方式描述如下：

［Searching］

（1）以H為頭指針，向后遍歷鏈表，訪問每個元素Cj;

（2）如果Cj對應的MBX與S相交，則進一步判斷Cj的類型：如果是原子，則直接將Cj添加到查找結果列表中，如果是子表，以子表的頭指針為H，遞歸調用查找算法［Searching］;

（3）如果Cj對應的MBX與S不相交，則指針后移一個元素，重復步驟2，直到j等于k為止。

2.2 插入算法

插入算法（Insert）是X-Lists的關鍵，是一種動態插入算法，設當前的X-Lists為CXL，其中已有k＋1個元素。現要在集合R中依次取出一個元素，順次插入CXL中。

［Insert］

（1）設當前取出的元素Ri∈R，首先計算Ri與C是否相交;

（2）如果不相交，并且k＜m－1，則將Ri作為CXL的表尾元素添加;

（3）如果不相交，并且k＝m－1，則將CXL作為表頭，Ri作為表尾，構建新的表，重新記為CXL;

（4）如果相交，并且存在Cj與Ri相交，則將Ri與Cj合并成新的Cj;這個合并過程是一個將Ri遞歸插入Cj中的過程，其終止條件是Ri插入Cj中的與Ri相交的子表中，或者直接成為Cj的原子元素，使得Cj本身也是一個X-Lists;

（5）如果相交，并且在CXL中不存在任何元素與Ri相交，若k＜m－1，則將Ri作為C的表尾元素添加;若k＝m－1，則將CXL作為表頭，Ri作為表尾，構建新的表，重新記為CXL，并調用［AdjustInsert］算法調整列表CXL;

（6）重復上述步驟，完成R集合的插入，也即完成X-Lists的構建過程。

按照上述插入算法，圖2中R8至R19的插入過程如下（當前插入元素用黑體表示）：

2.3 刪除算法

X-Lists的刪除分為兩種：第一種是給定一個空間對象的唯一標識，在列表中刪除該元素節點;第二種是給定一個區域，刪除列表中所有落在該區域中的元素節點，其可以由第一種算法多次執行得到。本文重點討論第一種動態刪除算法。

［Delete］

（1）設CXL中要刪除的空間對象為obj，調用［FindPath］算法，得到obj的路徑棧S;

（2）如果［FindPath］查找失敗，則表明CXL中沒有obj元素，直接返回，否則繼續;

（3）取出S的棧頂元素，賦值給head，pNode;

（4）如果S為空，則pNode是頂層表元素，在該層雙向鏈表中刪除節點pNode，重新計算總體包圍邊界;

（5）如果S不為空，則取S棧頂元素，賦值給pParentNode，則pParentNode是pNode的父表元素;

（6）在pNode所在的同級鏈表中刪除pNode，并獲取其頭節點head，令pParentNode→sublist指向h;

（7）如果head所在鏈表只有一個元素，則用head替換pParentNode，該步可以直接調用［AdjustDelete］算法實現;

（8）將S中的所有元素順次彈出，計算調整各個父表元素的包圍邊界，最后計算調整總包圍邊界后返回，該步可以直接調用［Adjust Boundary］算法實現。

2.4 其他輔助算法

在X-Lists中除了上述的查找（Searching）、刪除（Delete）、插入（Insert）3個主要算法外，還有一些輔助算法。

2.4.1 元素定位 定位算法（Find）主要實現在XLists中查找指定的空間對象所在的元素位置。設要定位的空間對象唯一標識為obj，需要返回obj對應的節點元素element及其父表元素parent＿element，具體算法描述如下：

2.4.2 路徑定位 路徑定位（FindPath）算法用于實現在一個X-Lists中查找指定的空間對象所在位置及從節點上溯到最頂層父表的所有各層級的父表元素構成的路徑。為實現該算法，首先實現［Find-Parents］算法。設要定位的空間對象為obj，當前列表的頭節點為head，head的上級父表節點為head＿parent，采用棧結構存儲父表節點路徑。

（8）如果上述步驟都無最終返回TRUE，則將棧頂元素出棧，返回FALSE。

（9）返回的棧內元素即為obj節點的各層級的父節點元素。

該算法采用遞歸方式實現了obj各個層級的父表節點，但在棧內沒有包含obj節點，［FindPath］算法則在此基礎上將obj找到，并壓棧處理。具體算法描述如下：

2.4.3 調整算法 調整算法［Adjust］主要針對XLists的動態插入、刪除過程中出現的一些異常情況進行處理和優化，是一個算法集合。在X-Lists的更新中常會涉及節點的包圍邊界的調整問題，本文給出指定節點邊界調整算法［AdjustBoundary］，該算法的輸入參數是一個路徑棧，棧頂元素為當前改動邊界范圍的節點元素。

（7）如果S不為空，重復執行步驟3～7，直到S為空;

（8）遍歷pNextTopNode所在鏈表，重新計算每個元素的邊界之和，賦值給X-Lists總邊界范圍。

上述邊界調整算法相對比較簡單，可以單獨成函數供調用，也可以在插入、刪除中直接嵌入。為了敘述清晰，在邊界調整的地方直接調用［Adjust-Boundary］。

圖3a顯示的是圖2的局部，如果刪除R14節點，則以R13為頭的鏈表只有一個節點，不符合X-Lists性質，需要進行調整，即把R13升級為其父表元素，并調整上層的包圍邊界，如圖3b所示。刪除過程中的調整算法描述如下：

（4）以S為參數，調用［AdjustBoundary］調整相關節點的包圍邊界;

（5）用pSubNode節點替換pNode節點。

圖3 刪除過程中的異常情況Fig.3 Anomalies in the process of deletion

圖4顯示了插入過程中經常出現一種異常情況。以圖2所示的數據為例，如果R17先于R10插入，按照［Insert］的步驟5，則會出現如圖4a所示情況，顯然不如圖4b所示的狀況好，因為R8、R9、R17構成的包圍邊界范圍遠大于R8、R9、R10構成的邊界范圍，如果不進行調整，會大大增加X-Lists中節點重疊率和X-Lists的深度。調整的原則是使各個節點對應的子表的邊界范圍盡可能最小。這種異常情況一般出現在［Insert］算法的步驟5中，設當前節點為pNode，待插入的節點為element（對應圖4a中的R10），如果element→bound與pNode→bound有重疊，不與pNode子表中的任何元素有重疊，并且pNode子表中的元素個數已經達到最大節點數m，在這種情況下則需要進行插入調整。

圖4 插入過程中的異常情況Fig.4 Anomalies in the process of inserting

針對這種情況，調整算法設計如下：

3 算法實驗與分析

為驗證算法的有效性，對本文提出的算法進行了實驗。實驗設備為Sony VGN-SR48J，Intel Core2 Duo CPU 2.53 GHz，內存2 GB，操作系統為 Windows XP。由于CSR-Tree是以R＊-Tree為基類實現的，其性能高于R＊-Tree，為此，本文選擇R-Tree和CSR-Tree與X-Lists進行對比分析，分別對RTree、CSR-Tree和X-Lists的構建算法和查找算法的時間和空間性能進行了測試。

測試數據集為隨機生成數據。X-Lists和RTree一樣，是一種動態多維空間索引結構，可以適用于高維查詢，本文重點對三維數據集進行測試，結果見表1。

表1 X-Lists、R-Tree與CSR-Tree測試結果Table 1 Experimental results of X-Lists，R-Tree and CSR-Tree

為了更清楚地看出效率差異，將上述數據處理成折線圖，見圖5～圖7。圖5顯示了R-Tree、CSRTree和X-Lists 3種索引結構的創建時間對比，隨著空間對象個數的增加，X-Lists與R-Tree創建索引的效率基本相當，CSR-Tree由于需要進行聚類、排序操作，所以CSR-Tree的創建耗時要明顯大于XLists和R-Tree。圖6顯示了R-Tree、CSR-Tree和X-Lists 3種索引占用內存空間情況的比較。由于CSR-Tree對數據集進行了聚類排序處理，因此CSR-Tree中的節點重疊率明顯低于R-Tree。因此，對于同樣的數據集，CSR-Tree的節點數要小于RTree，也即其內存占用量小于R-Tree的內存占用量，其節點數或內存占用量與空間對象數基本呈正比。X-Lists針對同一數據集創建的索引內存占用量小于CSR-Tree，明顯優于 R-Tree，如圖6所示。圖7是 R-Tree、CSR-Tree和 X-Lists 3種索引查詢效率的比較。由于CSR-Tree是對R＊-Tree的改進，隨著數據量的增加，CSR-Tree相對于R-Tree的查詢優勢會變大。對于同樣的隨機數據集和同樣的區域查詢，X-Lists查詢性能明顯高于CSR-Tree和R-Tree（圖7）。

圖5 索引創建耗時Fig.5 The time cost of index creation

4 結論

本文對基于廣義表的動態空間索引結構進行了研究，提出了一種新的動態索引結構X-Lists，設計實現了X-Lists的動態插入、動態刪除、查找等算法，并進行了算法實驗，結果表明：在內存空間占用方面，X-Lists的構建性能明顯優于R-Tree和CSRTree;在索引構建時間方面，X-Lists與 R-Tree相當，優于R＊-Tree和CSR-Tree;X-Lists的查詢性能在時間和空間占用上均明顯優于R-Tree和CSRTree。

此外，X-Lists是一種廣義表，R-Tree是 X-Lists的一個子集，能支持高維點查詢和區域查詢。由于廣義表的優良性質，X-Lists在具有高效的空間索引性能的同時，更有利于對大規模空間數據集進行空間關系推理，或將為基于索引結構的空間關系的智能推理提供新的實現思路和方法。

［1］何珍文.泛型聚類排序3DR樹批量構建算法［J］.地理與地理信息科學，2009，25（3）：12－15.

［2］HE Z W，WU C L，WANG C.Clustered sorting R-Tree：An index for multi-dimensional spatial objects［A］.GUO M Z，ZHAO L，WANG L P.Proceedings of 4th International Conference on Natural Computation（ICNC 2008）［C］.Jinan：IEEE Computer SOC，2008.348－352.

［3］何珍文.地質空間三維動態建模關鍵技術［D］.華中科技大學，2008.

［4］GUTTMAN A.R-Trees：A dynamic index structure for spatial searching［A］.YOUMARK B.Proc.of the ACM Int′l Conf.on Management of Data［C］.Boston：ACM Press，1984.47－57.

［5］張軍旗，周向東，王梅，等.基于聚類分解的高維度量空間索引B＋-Tree［J］.軟件學報，2008，19（6）：1401－1412.

［6］SELLIS T，ROUSSOPOULOS N，FALOUTSOS C.The R＋-Tree：A dynamic index for multi-dimensional objects［A］.VLDB［C］.1987.507－518.

［7］BECKMANN N，KRIEGEL H P，SCHNEIDER R，et al.The R＊-tree：An efficient and robust access method for points and rectangles［A］.CLIFFORD J，KING R.Proceedings of the ACM SIGMOD International Conference on the Management of Data［C］.Denver，Colorado：ACM Press，1991.322－331.

［8］KAMEL I，FALOUTSOS C.On packing R-Trees［A］.BHARAT B，TIM F，YELENA Y.Proceeding of the 2nd Conference on Information and Knowledge Management （CIKM）［C］.Washington DC，1993.490－499.

［9］KAMEL I，FALOUTSOS C.Hilbert R-Tree：An improved R

Tree using fractals［A］.BOCCA J B.Proceedings of the 20th International Conference on Very Large DataBases［C］.San Francisco：Morgan Kaufmann Publishers Inc，1995.500－509.

［10］周學海，李曦，龔育昌，等.多維向量動態索引結構研究［J］.軟件學報，2002，13（4）：768－773.

［11］HE Z W，LIU G，WU C L.R-Lists：A dynamic spatial index structure based on generalized lists［A］.2th International Conference on Future Computer and Communication［C］.2010，9（2）：553－556.

Dynamic Generalized List Spatial Index Method

HE Zhen－wen，ZHENG Zu－fang，LIU Gang，WU Chong－long
（SchoolofComputer，ChinaUniversityofGeosciences，Wuhan430074，China）

A new dynamic spatial indexing structure named X-Lists has been presented in this paper.The X-Lists algorithms including the dynamic insertion，dynamic deletion and searching algorithms have been designed and implemented，and the algorithm experiments have been carried out.X-Lists is a type of generalized lists which supports multi-dimensional point query and range query.Experimental results show that，X-Lists in the two aspects of construction and regional searching is superior to the existing R-Tree index structure and its improvement index structures.

spatial index;R-Tree;generalized lists;X-Lists

P208

A

1672－0504（2011）05－0009－07

2011－03- 18;

2011－05－06

國家自然科學基金項目（41101368）;教育部高校博士點基金項目（20100145110009）;中央高校基本科研業務費專項資金資助項目

何珍文（1978－），男，博士，副教授，主要研究領域為數據庫技術、空間信息科學與技術。E－mail：zwhe＠foxmail.com