一種全新的Ｒ樹節點選擇算法

收稿日期：2007-10-18；修回日期：2008-03-05

基金項目：國家自然科學基金資助項目(40571121)；江西省教育廳科技計劃資助項目（GJJ08152）；香港“數字志蓮凈苑木構佛寺演示系統”項目

作者簡介：龔俊(1978-)，男，湖北武漢人，博士，主要研究方向為空間數據庫、空間數據可視化(gongjunbox@gmail.com)；柯勝男(1981-)，女， 碩士，主要研究方向為軟件工程、程序設計；鮑曙明(1959-)，男，教授，博士，主要研究方向為時空分析建模.*

(1. 江西師范大學 a.鄱陽湖生態環境與資源研究教育部重點實驗室; b.軟件學院，南昌 330022；2. 密歇根大學

中國數據中心，Ann Arbor，Michigan 48109-1106)

摘 要：在R樹插入算法中采用全新的節點選擇算法，一改傳統的從根節點開始自上而下的節點選擇方案，而是從葉節點層開始，先自下而上再自上而下地選擇葉節點，較好地解決了同層節點重疊所導致的查詢效率低下的問題。實驗證明，提出的R樹空間索引方法，不僅在查詢效率上明顯優于R*樹，而且R樹生成的時間開銷也減少了50％左右，綜合性能超過了R*樹，便于擴展到三維甚至多維空間中，以實現對空間數據和時空數據的高效查詢功能。

關鍵詞：R樹;空間索引；空間數據庫；節點選擇

中圖分類號：TP311

文獻標志碼：A

文章編號：1001-3695(2008)10-2946-03

Brand-new node-choosing algorithm of R-tree spatial index

GONG Jun¹a， KE Sheng-nan¹b， BAO Shu-ming²

(1. a. Key Laboratory of Poyang Lake Ecological Environment Resource Development， b. School of Software， Jiangxi Normal University， Nanchang 330022， China；2. China Data Center， University of Michigan， Ann Arbor， MI 48109-1106， USA)

Abstract:Spatial index is a key technique in the field of spatial database. This paper presented a brand-new node-choosing algorithm in the insertion procedure of R-tree spatial index， which was greatly different from the classical algorithm. From the beginning of the leaf node layer， firstly from bottom to top then inversely， chose the right leaf node， and this scheme could solve the problems caused by node overlapping. A comparative performance analysis on the current and improved methods show that not only the query performance but also the generation performance of the improved method is higher than the current method such as R*-tree.Moreover， the improved method can be extended into the field of multi-dimension applications such as spatio-temporal application.

Key words：R-tree;spatial index;spatial database;node-choosing

0 引言

空間信息服務對人們生活產生日益重大的影響，空間數據因而成為最重要和普遍可得的數據類型之一。高效的空間數據管理方法隨之成為地理信息科學和計算機領域的研究熱點。空間查詢是空間數據管理的重要操作之一。它是給定一個空間范圍查詢條件，搜索空間數據集中滿足查詢條件的空間對象。二十多年來，大量的研究關注于為空間數據庫建立索引數據結構以提升空間查詢效率，即空間索引[1]。然而類似于Google Earth虛擬地球系統的PB級(1 PB=1 024 TB=1 024×1 024 GB)海量空間數據庫的出現，給空間數據管理方法提出了更為嚴格的要求，亟待提出更為高效的空間索引算法以提高空間查詢效率。現階段的空間索引方法至少應具備如下特性[2]：

a)具備動態結構。適應空間對象數據的任意插入和刪除操作。

b)適應二級存儲管理。執行空間查詢操作時，僅需部分加載所需的索引數據，最大限度地減少內存資源損耗。

c)擴展性強。效率不明顯受數據庫規模的影響。

d)時間效率高。空間查詢執行效率高。

e)空間效率高。空間索引結構的數據量可以忽略不計。

R樹索引方法具備上述特點，廣泛地被國內外知名系統所采用，其中包括ESRI地理信息系統平臺，被公認為空間查詢綜合性能最佳的索引方法。R樹是一維數據索引B樹在多維空間中的自然擴展，有效解決非點狀多維空間對象的查詢問題，是一種深度平衡的樹狀索引數據結構，即根節點到任何包含索引記錄的葉節點的深度相等，從而保證R樹性能穩定和合理利用存儲空間。自從Guttman[3]提出R樹索引的原創思想以來，經過專家學者二十年來的研究和改進，現已產生了多達數十個R樹變種，形成了一個龐大的R樹體系[4]。所有的R樹變種始終包含一個重要子過程，即R樹插入操作。通過R樹插入算法，新對象被逐一插入R樹，形成合理的R樹樹型，以提高空間查詢性能。

R樹插入算法包含兩個重要子算法，即節點選擇和節點分裂。節點選擇算法旨在將插入的對象提供最鄰近的樹葉節點來包含待插入的對象；節點分裂算法旨在將因插入操作導致上溢的節點分為數個小節點，盡可能保持空間聚簇特性。兩個子算法吸取空間聚簇的思想，使得空間相鄰的對象存儲于相同或相鄰的節點中，以保證樹型的合理性。節點選擇算法傾向于從全局角度優化樹型，因為它是從根節點開始在全樹范圍搜索合理的葉節點；而節點分裂算法傾向于從局部角度優化樹型，因為它是從葉節點開始進行局部分裂操作。兩者從不同的角度全面優化了R樹樹型。

傳統R樹插入算法均是從根節點開始向下搜索，直至找到適合插入的葉節點。它采用的是一種自上而下的搜索方案，但是這往往不能獲得最為合適的節點。為此本文提出一種改進的R樹插入算法，采用了全新的節點選擇算法和一種先自下而上、后自上而下的葉節點搜索方案，相對于原有算法明顯地優化了R樹樹型結構，顯著提升了R樹的空間查詢性能。

1 改進的R樹插入算法

R樹插入算法是生成合理樹型的重要步驟，其中包含節點選擇和節點分裂兩個子過程。絕大多數R樹變種在節點分裂算法上作改進，而節點選擇算法始終沒有大的變化，一般均是延續從根節點開始、層層搜索直至葉節點的經典思路。實際上，節點分裂操作是對R樹最末端的上溢葉節點實施分裂，僅從局部角度優化樹型，即使是綜合性能最優變種R*樹也僅是通過增加插入次數來提高插入操作的合理性，不是從整個R樹的角度來改善樹型；節點選擇操作則是從R樹根節點開始，全面地搜索合適的葉節點，在優化R樹樹型方面相比節點分裂操作來說作用更大[5]。本文提出改進的R樹插入算法，主要是采用一種全新的節點選擇算法，而節點分裂算法其余部分仍然沿用經典R樹索引算法。

11 傳統方法存在的問題

經典R樹的節點選擇算法中，對象首先進入根節點，從中選擇加入對象后空間范圍增長最少的子節點作為對象下一步進入的節點，如此迭代計算直至到達葉節點，選擇該葉節點作為對象的插入歸屬。R*樹甚至引入了重疊范圍作為選擇節點的標準。上述方法旨在將對象插入到最鄰近的葉節點內，然而實際上在許多情況下并不能夠搜索到最合適的節點。

圖1用于說明現有節點選擇算法不能有效處理的情況，待插入的索引對象落于兩個節點的重疊區域時，如果按照空間范圍和重疊范圍增長最小的判斷原則，則對象插入操作對兩個節點的影響是完全相同的，但是左上方節點中的子對象與即將插入的對象更為鄰近，所以插入左上方節點是更優方案。現實中R樹重疊現象不可避免，因此圖中情況較為普遍，優化算法針對該問題提出了解決方案。

12 全新的節點選擇算法

上面對現有R樹節點選擇算法存在的問題進行了理論分析，下面針對存在的問題提出改進的節點選擇算法。如果以根節點為上，以葉節點為下，傳統的節點選擇算法自上而下地逐級選擇合適節點直至葉節點。前面已經分析過這種方式的弊端，因此，本文采用一種先自下而上、再自上而下的方式選擇合適的葉節點來插入對象。算法入口，首先從葉節點所在層開始搜索完全包含待插入對象的節點；如果搜索結果不為空，即存在完全包含對象的葉節點，則在搜索結果中選擇合適的節點作為最終節點；如果搜索結果為空，在上面一層中搜索完全包含待插入對象的節點。如果搜索結果不為空，則在搜索結果中選擇合適的節點作為新的根節點，調用類似于傳統的節點選擇算法自上而下地選擇合適的葉節點，如果搜索結果仍然為空，則在更上一層搜索完全包含對象的節點。依此類推，直到根節點為止。圖2是改進算法的步驟流程。

節點選擇的優化算法描述如下：

算法入口 待插入的對象obj和R樹的根節點root:

算法出口 最終插入對象的R樹葉節點。

a)計算R樹的樹高為depth，假設根節點的層號是0，樹葉節點的層號是depth-1，令當前層號L=depth-1，即樹葉節點所在層。

b)運用R樹查詢算法，查找第L層中完全包含對象obj的所有節點，其查詢結果集合S＝{node0，node1，… ，noden-1 }。

c)如果集合S為空，且L≠0，即當前層不為根節點層時，則令L＝L－1，進入b)；否則，進入d)。

d)如果集合S為空，且L＝0，即當前層為根節點層時，則令R樹根節點root為f)的入口條件，進入f)；否則，進入e)。

e)如果集合S不為空，表示對象obj完全落于一個以上的節點中。其中，當L=depth-1時，即當前層為葉節點層時，選擇集合S中覆蓋范圍最小的節點N作為本算法出口的輸出結果，退出算法；當L≠depth-1時，即當前層不為葉節點層時，集合S中所有節點包含的直接孩子節點的集合child_set={child0，child1，… ，childm-1}，將對象obj分別插入到child_set中的每個節點，選擇覆蓋范圍與其他孩子節點的重疊范圍之和W增長最小的孩子節點childi作為f)的入口條件，進入f)。

f)以d)或者e)傳入的節點作為根節點N。

g)如果N是葉節點，進入i);如果N不是葉節點，則進入h)。

h)N的子節點集合set為{child0，child1，… ，childn-1}。從集合set中選擇插入obj后覆蓋范圍以及與其他子節點的重疊范圍之和W增長最小的子節點childi。一旦存在多個節點具有相同W最小值，則選擇覆蓋范圍最小的子節點childi。令childi為N，重新進入g)。

i)返回N作為本算法出口的輸出結果，退出算法。

2 實驗結果分析

21 常規二維空間查詢效率測試

自從R樹索引誕生以來，經過二十多年的演化發展，普遍認為R*樹是綜合性能最優的R樹索引方法[5]。為此，本文將新算法與R*樹索引方法進行比較，以檢驗新算法的查詢效率。本文采用三份測試數據，測試數據采用隨機過程生成。每份測試數據中包含了不同數量規模的對象集合，滿足不同規模數據庫的應用要求，而且每個對象的尺寸不盡相同，符合現實情況；同時采用不同大小的空間范圍作為查詢條件來實施測試。實驗環境為Core2 Duo T7500 CPU（主頻2.2 GHz），2 GB DDR2內存和160 GB B5400RPM IDE硬盤的筆記本電腦；測試代碼使用C++語言實現；操作系統為Windows XP專業版。表1是三份測試數據的描述信息。

表1 三份測試數據的描述信息名稱場景范圍尺寸

（x×y，m×m）對象數目

/個對象邊長

/m數據11 000×1 00010 0001～10數據21 000×1 00050 0001～10數據31 000×1 000100 0001～10

測試工作涉及兩種典型的空間查詢，即區域查詢和點查詢。對于區域查詢，按照相對于整個場景的空間范圍的比例，區域查詢的范圍分為0.01％、0.1%和1%三項。點查詢以及不同尺寸區域的區域查詢等四種查詢，每種查詢都進行了1 000次查詢操作，以便獲得客觀的統計值。三份測試數據的區域查詢和點查詢的實驗結果如表2所示，其中的測試數據是1 000次查詢的時間總和。除查詢效率外，插入算法的性能也是普遍關注的問題，關系到R樹的構造效率。表3是三份模型數據插入過程的測試結果，記錄了R樹生成的時間開銷。

表2 三份測試數據的查詢時間測試數據算法區域查詢0.01%0.1%1%點查詢數據1R*樹0.110 10.180 90.267 50.070 0改進算法0.015 80.036 90.131 00.005 8數據2R*樹0.580 90.983 41.478 10.348 3改進算法0.088 30.114 80.576 20.050 9數據3R*樹1.195 11.801 12.768 80.740 7改進算法0.132 30.237 91.253 70.069 0表3 R樹生成的時間開銷算法數據名稱測試數據1測試數據2測試數據3R*樹0.598 93.583 17.755 5改進算法0.284 22.012 14.515 4

盡管采用的是相同的查詢算法，時間復雜度為O(M×log(N))（其中:M為每個節點中包含子節點的最大數目;N是對象的總數目），然而在查詢性能方面，本文提出的改進算法優于R*樹，生成的R樹樹型更為合理。總的來說，改進算法查詢性能至少提高2倍以上，而且，隨著查詢范圍越小，查詢性能提高得越明顯，如點查詢的效率甚至提高了10倍以上。改進算法中的節點選擇算法的最大時間復雜度為O(M×log(N)×log(N))，傳統算法的時間復雜度為O(M×log(N))，然而，改進算法的插入效率有明顯提高，R樹生成效率幾乎提高了1倍。究其原因，主要是因為樹型始終保持合理，對象自始至終被插入到最為合理的節點中，節點分裂操作得以大量減少，從而改善了插入算法的效率。為了形象地說明所生成R樹樹型的合理性，本文將算法擴展到三維空間，采用三維圖形來說明算法優越性。

圖3是新舊算法生成三維R樹的效果對比圖。圖中線框表示同層節點的最小包圍盒（MBR），新R樹算法構建的樹型(圖3（b）)，相對于舊算法(圖3（a）)來說大為改善，重疊現象基本消除，三維MBR的三個邊長基本均勻，同層節點的尺寸也基本均勻。改進后的樹型有助于改善多路查詢的問題，從而提高空間查詢性能。圖4是三維R樹的不同層節點描述，這棵R樹總共存在四層節點。

22 三維空間查詢效率測試

為滿足日益增加的真三維空間應用的查詢需求，本文將改進算法擴展到三維空間。下面采用三份不同類型的真三維空間數據進行查詢效率測試，目的在于更為客觀全面地測試R樹效果。測試軟硬件平臺同上述二維查詢效率測試。

三維數據的真實效果如圖5所示。表4列出圖5的三份模型數據的細節描述。第一和第二份模型數據相當復雜，在狹小的空間內包含不同尺寸和形狀的建筑構件；第三份模擬數據中構件的形狀和尺寸比較接近和均勻。

表4 三分模型數據的描述信息

模型類型參考圖像構件數目場景尺寸 (x×y×z， m3)殿模型圖 5（a）9 28233.6×24.6×15.8塔模型圖 5（b）3 51813.7×13.6×32.7模擬數據圖 5（c）20 0001 000×1 000×1 000

測試工作涉及兩種典型的空間查詢區域查詢和點查詢。對于區域查詢，相對于整個模型場景的空間范圍，區域查詢的范圍分為1％、0.1%和0.01%三項。點查詢以及不同尺寸區域的區域查詢等四種查詢，每種查詢都進行了1 000次查詢操作，以便獲得客觀的統計值。三份模型數據的區域查詢和點查詢的實驗結果如表5所示。其中的測試數據是1 000次查詢的時間總和。

表5 殿模型的查詢時間算法區域查詢0.01%0.1%1%點查詢R*樹0.093 40.189 30.523 50.064 8改進算法0.032 50.089 30.341 30.018 7R*樹0.029 40.034 50.153 90.020 4改進算法0.009 30.010 80.108 70.006 9R*樹0.693 61.084 31.886 40.438 7改進算法0.028 60.086 20.347 60.018 8

從測試數據中新舊算法的對比中不難看出，三維空間查詢測試仍然保持與二維空間查詢相類似的結果，改進算法的查詢效率至少提高50％以上，點查詢和小區域查詢的效率改進更為明顯。

上述算法已經應用于香港志蓮凈苑三維仿真系統中，較為明顯地改善了三維實時漫游過程中動態查詢和實時調度的系統效率。該仿真系統要求三維建模精度甚高，要求達到近景瀏覽時與實物保持一致的效果。系統界面和三維漫游效果如圖6所示。

3 結束語

空間數據庫規模日益膨脹，對空間索引技術提出了越來越嚴格的要求。支持二級緩存、查詢效率高、可擴展性成為新一代空間索引技術的重要特征。本文提出的先自下而上、再自上而下的節點選擇算法，不僅使R樹插入算法生成的R樹樹型更為合理，而且還提高了R樹生成效率，綜合性能全面超越了原有R*樹，符合當前對空間索引方法的應用要求，滿足超大規模空間數據庫管理的需要。

隨著空間應用逐漸發展到三維空間應用和四維時空應用階段，R樹索引同樣也要能夠提供對三維空間數據和四維時空數據的索引功能[6]。并且，信息分類、數據挖掘和人工智能等領域對高維抽象數據的查詢和管理需求也尤其迫切，還需要進一步研究R樹空間索引擴展至高維空間的問題，解決R樹索引擴展到高維空間時性能急劇惡化的難題[7]。同時，目前超大規模的空間數據往往被部署于計算機集群中，因此還需要研究R樹索引的并行查詢算法，利用計算機集群來提高空間數據管理性能[8]。在分布式多用戶環境中，為保證多個用戶同時對一個索引結構進行查詢、插入和刪除操作而不發生沖突，空間數據庫環境下基于R樹的并發控制機制也是一個亟待研究的領域[9]。這些問題的有效解決將關系到本索引方法是否能夠成功地與實際應用相結合，在更為廣泛的領域得到發展。

參考文獻：

[1]吳立新，史文中. 地理信息系統原理與算法[M]. 北京:科學出版社， 2003.

[2]GAEDE V， GNTHER O. Multidimensional access methods[J]. ACM Computing Surveys， 1998， 30(2): 170-231.

[3] GUTTMAN A. R-trees: a dynamic index structure for spatial sear-ching[C]//Proc of ACM SIGMOD 1984.New York:ACM Press，1984:47-57.

[4]張明波，陸鋒，申排偉，等. R樹家族的演變和發展[J]. 計算機學報， 2005， 28(3):289-300.

[5]BECKMANN N. The R*-tree: an efficient and robust access method for points and rectangles[C]//Proc of ACM SIGMOD Int Conf on Management of Data. New York:ACM Press， 1990:322-331 .

[6]CHO H， CHUNG C W. Indexing range sum queries in spatio-temporal databases[J]. Information and Software Technology， 2007， 49(4):324-331.

[7]CHEN L， CHOUBEY R. Merging R-trees: efficient strategies for local bulk insertion[J]. Geoinformatica， 2002， 6(1):7-34 .

[8]SHEKHAR S， CHAWLA S. Spatial databases: a tour[M]. New Jersey:Prentice Hall， 2002.

[9]NING A， JI J， ANAND S. Toward an accurate analysis of range queries on spatial data[J]. IEEE Trans on Knowledge and Data Engineering， 2003， 15(2):305-323.