【轉載】R-Tree空間索引演算法的研究歷程和最新進展分析2008-07-09 23:15摘要：本文介紹了空間索引的概念、R-Tree資料結構和R-Tree空間索引的演算法描述,並從R-Tree索引技術的優缺點對R-Tree的改進結構——變種R-Tree進行了論述.最後,對R-Tree的最新研究進展進行了分析.

關鍵詞：空間索引技術；R-Tree；研究歷程；最新進展

當前資料搜尋的一個關鍵問題是速度.提高速度的核心技術是空間索引.空間索引是由空間位置到空間物件的對映關係.當前的一些大型資料庫都有空間索引能力,像Oracle,DB2.

空間索引技術並不單是為了提高顯示速度,顯示速度僅僅是它所要解決的一個問題.空間索引是為空間搜尋提供一種合適的資料結構,以提高搜尋速度.

空間索引技術的核心是：根據搜尋條件,比如一個矩形,迅速找到與該矩形相交的所有空間物件集合.當資料量巨大,矩形框相對於全圖很小時,這個集合相對於全圖資料集大為縮小,在這個縮小的集合上再處理各種複雜的搜尋,效率就會大大提高.

所謂空間索引,就是指依據空間實體的位置和形狀或空間實體之間的某種空間關係,按一定順序排列的一種資料結構,其中包含空間實體的概要資訊如物件的標識、外接矩形及指向空間實體資料的指標.簡單的說,就是將空間物件按某種空間關係進行劃分,以後對空間物件的存取都基於劃分塊進行.

1 引言

空間索引是對儲存在介質上的資料位置資訊的描述,用來提高系統對資料獲取的效率.空間索引的提出是由兩方面決定的：其一是由於計算機的體系結構將存貯器分為記憶體、外存 兩種,訪問這兩種儲存器一次所花費的時間一般為30~40ns,8~10ms,可以看出兩者相差十 萬倍以上,儘管現在有“記憶體資料庫”的說法,但絕大多數資料是儲存在外存磁碟上的,如果對磁碟上資料的位置不加以記錄和組織,每查詢一個數據項就要掃描整個資料檔案,這種訪問磁碟的代價就會嚴重影響系統的效率,因此係統的設計者必須將資料在磁碟上的位置加以記錄和組織,透過在記憶體中的一些計算來取代對磁碟漫無目的的訪問,才能提高系統的效率,尤其是GIS涉及的是各種海量的複雜資料,索引對於處理的效率是至關重要的.其二是GIS 所表現的地理資料多維性使得傳統的B樹索引並不適用,因為B樹所針對的字元、數字等傳統資料型別是在一個良序集之中,即都是在一個維度上,集合中任給兩個元素,都可以在這個維度上確定其關係只可能是大於、小於、等於三種,若對多個欄位進行索引,必須指定各個欄位的優先順序形成一個組合欄位,而地理資料的多維性,在任何方向上並不存在優先順序問題,因此B樹並不能對地理資料進行有效的索引,所以需要研究特殊的能適應多維特性的空間索引方式.

1984年Guttman發表了《R樹:一種空間查詢的動態索引結構》,它是一種高度平衡的樹,由中間節點和頁節點組成,實際資料物件的最小外接矩形儲存在頁節點中,中間節點透過聚集其低層節點的外接矩形形成,包含所有這些外接矩形.其後,人們在此基礎上針對不同空間運算提出了不同改進,才形成了一個繁榮的索引樹族,是目前流行的空間索引.

R樹是B樹向多維空間發展的另一種形式,它將空間物件按範圍劃分,每個結點都對應一個區域和一個磁碟頁,非葉結點的磁碟頁中儲存其所有子結點的區域範圍,非葉結點的所有子結點的區域都落在它的區域範圍之內；葉結點的磁碟頁中儲存其區域範圍之內的所有空間物件的外接矩形.每個結點所能擁有的子結點數目有上、下限,下限保證對磁碟空間的有效利用,上限保證每個結點對應一個磁碟頁,當插入新的結點導致某結點要求的空間大於一個磁碟頁時,該結點一分為二.R樹是一種動態索引結構,即：它的查詢可與插入或刪除同時進行,而且不需要定期地對樹結構進行重新組織.

2 R-Tree資料結構

R-Tree是一種空間索引資料結構,下面做簡要介紹：

（1）R-Tree是n 叉樹,n稱為R-Tree的扇（fan）.

（2）每個結點對應一個矩形.

（3）葉子結點上包含了小於等於n 的物件,其對應的矩為所有物件的外包矩形.

（4）非葉結點的矩形為所有子結點矩形的外包矩形.

R-Tree的定義很寬泛,同一套資料構造R-Tree,不同方可以得到差別很大的結構.什麼樣的結構比較優呢?有兩標準：

（1）位置上相鄰的結點儘量在樹中聚集為一個父結點.

（2）同一層中各兄弟結點相交部分比例儘量小.

R樹是一種用於處理多維資料的資料結構,用來訪問二維或者更高維區域物件組成的空間資料.R樹是一棵平衡樹.樹上有兩類結點：葉子結點和非葉子結點.每一個結點由若干個索引項構成.對於葉子結點,索引項形如(Index,Obj_ID).其中,Index表示包圍空間資料物件的最小外接矩形MBR,Obj_ID標識一個空間資料物件.對於一個非葉子結點,它的索引項形如(Index,Child_Pointer). Child_Pointer 指向該結點的子結點.Index仍指一個矩形區域,該矩形區域包圍了子結點上所有索引項MBR的最小矩形區域.一棵R樹的示例如圖所示：

3 R-Tree演算法描述

演算法描述如下：

物件數為n,扇區大小定為fan.

（1）估計葉結點數k=n/fan.

（2）將所有幾何物件按照其矩形外框中心點的x值排序.

（3）將排序後的物件分組,每組大小為 *fan,最後一組可能不滿員.

（4）上述每一分組內按照幾何物件矩形外框中心點的y值排序.

（5）排序後每一分組內再分組,每組大小為fan.

（6）每一小組成為葉結點,葉子結點數為nn.

（7）N=nn,返回1.

4 R-Tree空間索引演算法的研究歷程

1 R-Tree

多維索引技術的歷史可以追溯到20世紀70年代中期.就在那個時候,諸如Cell演算法、四叉樹和k-d樹等各種索引技術紛紛問世,但它們的效果都不盡人意.在GIS和CAD系統對空間索引技術的需求推動下,Guttman於1984年提出了R樹索引結構,發表了《R樹:一種空間查詢的動態索引結構》,它是一種高度平衡的樹,由中間節點和頁節點組成,實際資料物件的最小外接矩形儲存在頁節點中,中間節點透過聚集其低層節點的外接矩形形成,包含所有這些外接矩形.其後,人們在此基礎上針對不同空間運算提出了不同改進,才形成了一個繁榮的索引樹族,是目前流行的空間索引.

2 R+樹

在Guttman的工作的基礎上,許多R樹的變種被開發出來, Sellis等提出了R+樹,R+樹與R樹類似,主要區別在於R+樹中兄弟結點對應的空間區域無重疊,這樣劃分空間消除了R樹因允許結點間的重疊而產生的“死區域”（一個結點內不含本結點資料的空白區域）,減少了無效查詢數,從而大大提高空間索引的效率,但對於插入、刪除空間物件的操作,則由於操作要保證空間區域無重疊而效率降低.同時R+樹對跨區域的空間物體的資料的儲存是有冗餘的,而且隨著資料庫中資料的增多,冗餘資訊會不斷增長.Greene也提出了他的R樹的變種.

3 R*樹

在1990年,Beckman和Kriegel提出了最佳動態R樹的變種——R*樹.R*樹和R樹一樣允許矩形的重疊,但在構造演算法R*樹不僅考慮了索引空間的“面積”,而且還考慮了索引空間的重疊.該方法對結點的插入、分裂演算法進行了改進,並採用“強制重新插入”的方法使樹的結構得到最佳化.但R*樹演算法仍然不能有效地降低空間的重疊程度,尤其是在資料量較大、空間維數增加時表現的更為明顯.R*樹無法處理維數高於20的情況.

4 QR樹

QR樹利用四叉樹將空間劃分成一些子空間,在各子空間內使用許多R樹索引,從而改良索引空間的重疊.QR樹結合了四叉樹與R樹的優勢,是二者的綜合應用.實驗證明：與R樹相比,QR樹以略大（有時甚至略小）的空間開銷代價,換取了更高的效能,且索引目標數越多,QR樹的整體效能越好.

5 SS樹

SS樹對R*樹進行了改進,透過以下措施提高了最鄰近查詢的效能：用最小邊界圓代替最小邊界矩形表示區域的形狀,增強了最鄰近查詢的效能,減少將近一半儲存空間；SS樹改進了R*樹的強制重插機制.當維數增加到5是,R樹及其變種中的邊界矩形的重疊將達到90％,因此在高維情況（≥5）下,其效能將變的很差,甚至不如順序掃描.

6 X樹

X樹是線性陣列和層狀的R樹的雜合體,透過引入超級結點,大大地減少了最小邊界矩形之間的重疊,提高了查詢效率.X樹用邊界圓進行索引,邊界矩形的直徑（對角線）比邊界圓大,SS樹將點分到小直徑區域.由於區域的直徑對最鄰近查詢效能的影響較大,因此SS樹的最鄰近查詢效能優於R*樹；邊界矩形的平均容積比邊界圓小,R*樹將點分到小容積區域；由於大的容積會產生較多的覆蓋,因此邊界矩形在容積方面要優於邊界圓.SR樹既採用了最小邊界圓（MBS）,也採用了最小邊界矩形（MBR）,相對於SS樹,減小了區域的面積,提高了區域之間的分離性,相對於R*樹,提高了鄰近查詢的效能.

5 R-Tree空間索引演算法的最新研究

資訊的膨脹使資料庫檢索需要面對的問題越來越多.在構建索引方面,最主要面臨的則是如何構造高效的索引演算法來支援各種資料庫系統（比如：多媒體資料庫、空間資料庫等）,特別是如何有效的利用演算法來實現加速檢索.概括地說,R-Tree空間索引演算法的研究要做到：支援高維資料空間；有效分割資料空間,來適應索引的組織；高效的實現多種查詢方式系統中的統一.R-Tree的索引結構最新研究不能是單純為了加速某種查詢方式或提高某個方面的效能,忽略其他方面的效果,這樣可能會造成更多不必要的效能消耗.

XML作為可擴充套件的標示語言,其索引方法就是基於傳統的R-Tree索引技術的XR-Tree索引方法.該方法構造了適合於XML資料的索引結構.XR-Tree索引方法是一種動態擴充記憶體的索引資料結構,針對XISS（XML Indexing and Storage System：XML索引和儲存體系）中結構連線中的問題,設計了基於XR-Tree索引樹有效地跳過不參與匹配的元素的連線演算法.但這種索引方法在進行路徑的連線運算中仍然儲存大量的中間匹配結果,為此一種基於整體查詢模式的基於索引的路徑連線演算法提出,即利用堆疊連結串列來臨時壓棧儲存產生的部分匹配結果,並且隨著匹配的動態進行出棧操作.這樣在查詢連線處理完成以後,直接輸出最終結果,既節省了儲存空間又提高了操作效率.