R樹

R樹是用來做空間數據存儲的樹狀數據結構。例如給地理位置，矩形和多邊形這類多維數據建立索引。R樹是由Antonin Guttman於1984年提出的。人們隨後發現它在理論和套用方面都非常實用。 在現實生活中，R樹可以用來存儲地圖上的空間信息，例如餐館地址，或者地圖上用來構造街道，建築，湖泊邊緣和海岸線的多邊形。然後可以用它來回答“查找距離我2千米以內的博物館”，“檢索距離我2千米以內的所有路段”（然後顯示在導航系統中）或者“查找（直線距離）最近的加油站”這類問題。R樹還可以用來加速使用包括大圓距離在內的各種距離度量方式的最鄰近搜尋。

基本介紹

• 中文名：R樹
• 外文名：R-Tree
• 提出者：Antonin Guttman
• 提出時間：1984年
• 套用學科：計算機
• 適用領域範圍：軟體，數據結構
• 適用領域範圍：多維索引

簡介

近二十多年來，許多學者致力於R樹的研究，在R樹的基礎上衍生出了許多變種。比較典型的有R+樹、R*樹、壓縮R樹等。

一棵R樹滿足的性質

1.除根結點之外，所有非根結點包含有m至M個記錄索引（條目）。根結點的記錄個數可以少於m。通常，m=M/2。

2.對於所有葉子中存儲的記錄（條目），I是最小的可以在空間中完全覆蓋這些記錄所代表的點的矩形（注意：此處所說的“矩形”是可以擴展到高維空間的）。

3.對於所有非葉子結點上的記錄（條目），i是最小的可以在空間上完全覆蓋這些條目所代表的點的矩形（同性質2）。

4.所有葉子結點都位於同一層，因此R樹為平衡樹。

變體

• R*樹
  
• R+樹
  
• Hilbert R樹
  
• X樹
  

原理

R樹的核心思想是聚合距離相近的節點並在樹結構的上一層將其表示為這些節點的最小外接矩形，這個最小外接矩形就成為上一層的一個節點。R樹的“R”代表“Rectangle（矩形）”。因為所有節點都在它們的最小外接矩形中，所以跟某個矩形不相交的查詢就一定跟這個矩形中的所有節點都不相交。葉子節點上的每個矩形都代表一個對象，節點都是對象的聚合，並且越往上層聚合的對象就越多。也可以把每一層看做是對數據集的近似，葉子節點層是最細粒度的近似，與數據集相似度100%，越往上層越粗糙。

一個二維矩陣上的R樹的例子

跟B樹類似，R樹也是平衡樹（所以所有葉子節點都在同一深度）。它把數據按（記憶體）頁存儲，是為磁碟存儲設計的（跟資料庫的做法相同）。每一頁可以存儲不超過一個上限的條目，這個上限一般用{\displaystyle M}表示。R樹會在除根節點以外的節點上維持數據條目不小於最小條目數。根據經驗，最小條目數在條目上限的30%–40%時性能最佳，而B樹會維持條目上限的50%，B*樹甚至維持條目上限的66%。這么做的原因是平衡空間數據比平衡B樹上的線性數據更複雜。

跟其他樹結構一樣，R樹的搜尋算法（例如：交集，子集，最鄰近搜尋）也非常簡單。核心思想是畫出查詢語句相應的框線，並用它來決定要不要搜尋某個子樹。這樣在搜尋時可以跳過樹上的大部分節點。跟B樹類似，這個特性讓R樹可以把整棵樹放在磁碟里，在需要的時候再把節點讀進記憶體頁，從而可以套用在大數據集和資料庫上。

R樹的主要難點在於構建一棵既能保持平衡（所有葉子節點在同一層），又能讓樹上的矩形既不包括太多空白區域也不過多相交（這樣在搜尋的時候可以處理儘量少的子樹）的高效的樹。例如，最初的通過插入節點來構建一棵高效的R樹的構想是選擇一棵子樹插入，使得對其外接矩形的擴張最小。填滿一頁後，把數據分成兩份，使它們分別包括儘量小的區域。大部分關於R樹的研究和改進都是關於如何改進建樹的過程。它們可以分為兩類，一類是如何從頭開始構建一棵高效的樹（被稱為批量載入），另一類是如何在一棵已經存在的樹上插入和刪除。

R樹不保證最壞情況下的性能，但是在現實數據上一般表現不錯。理論上來說，批量載入的優先權R樹是最壞情況下的最優解，但由於複雜度太高，還沒有在實際套用中獲得關注。

當數據被構建成R樹時，任意Lp空間中的數據的最近k個鄰居都可以很高效地用空間交集計算。這對很多基於最近鄰居法的算法（例如本地異常因子算法）都很有幫助。DeLi-Clu提出的Density-Link-Clustering是一種使用R樹來進行空間交集，從而高效地計算OPTICS聚類的聚類分析算法.

特點

R樹是一個高度平衡樹，它是B樹在k維上的自然擴展，用空間對象的MBR來近似表達空間對象，根據地物的MBR建立R樹，可以直接對空間中占據一定範圍的空間對象進行索引。R樹的每一個結點都對應著磁碟頁D和區域I，如果結點不是葉結點，則該結點的所有子結點的區域都在區域I的範圍之內，而且存儲在磁碟頁D中。如果結點是葉結點，那么磁碟頁D中存儲的將是區域I範圍內的一系列子區域，子區域緊緊圍繞空間對象，一般為空間對象的外接矩形。

R樹中每個結點所能擁有的子結點數目是有上下限的。下限保證索引對磁碟空間的有效利用，子結點的數目小於下限的結點將被刪除，該結點的子結點將被分配到其他的結點中；設立上限是因為每一個結點只對應一個磁碟頁，如果某個結點要求的空間大於一個磁碟頁，那么該結點就要被劃分為兩個新的結點，原來結點的所有子結點將被分配到這兩個新的結點中。令M為一個結點中記錄數目的最大值，mSM/2為一參數，說明一個節點記錄的最小值，m可作為調節樹結構的一個可變參數，R樹滿足如下幾項特點：

1．根節點若非葉子節點，則至少有兩個子節點；

2．每個非根葉節點和非葉節點包含的實體個數均介於m和M之間；

3．所有葉子節點在同一層次；

R樹兄弟結點對應的空間區域可以重疊，可以較容易地進行插入和刪除操作。但正因為區域之間有重疊，空間索引可能要對多條路徑進行搜尋後才能得到最後的結果。當查找與給定的查詢視窗相交的所有空間對象時，空間搜尋算法是從根結點開始，向下搜尋相應的子樹．算法遞歸遍歷所有約束矩形與查詢視窗相交的子樹，當到達葉結點時，邊界矩形中的元素被取出並測試其是否與查詢矩形相交，所有與查詢視窗相交的葉結點即為要查找的空間對象。R樹的查詢效率會因重疊區域的增大而大大減弱，在最壞情況下，其時間複雜度甚至會由對數搜尋退化成線性搜尋。正是這個原因促使了R+樹的產生。

在R+樹中，兄弟結點對應的空間區域沒有重疊，而沒有重疊的區域劃分可以使空間索引搜尋的速度大大提高，克服了R樹中多路查詢的問題，但同時它也存在著一些缺陷，如對某個最小約束矩形的劃分，可能會引起相關子樹上其他結點也需要重新劃分，向下分裂操作可能使得已經劃分好了的結點被重新劃分，空間對象在R+樹的葉結點中被重複標記，完成刪除運算後，必須對R+樹進行重建等，同時由於在插入和刪除空間對象時要保證兄弟結點對應的空間區域不重疊，而使插入和刪除操作的效率降低。

R*樹是最有效的R樹變種，它能對覆蓋區域、重疊面積和邊界周長進行啟發式地最佳化，並通過重新插入節點重建R．樹以提高其性能，但重新插入這個過程相當繁瑣，其實現過程太過漫長。壓縮R樹的空間數據集是預先己知的，通過預先對數據進行合理有效的組織，可以保證其具有很高的空間利用率和良好的查詢效率，但由於其不能進行動態插入和刪除，因而其套用受到了很大限制。

R樹是B樹在多維空間的擴展，是一種平衡的樹結構。R樹結構採用平行於數據空間軸的最小的邊界矩形來近似複雜的空間對象，其主要優點是用一定數量的位元組來表示一個複雜的對象。儘管這樣會丟失很多的信息，但是空間物體的最小邊界矩形保留了物體的最重要的幾何特性，即空間物體的位置和其在整個坐標軸上的範圍。

算法

數據格式

R樹的數據按（記憶體）頁存儲，每一頁存儲多條數據，數據條數不超過一個事先定義的最大值，一般會多於最小值。非葉子節點上的每一條數據由指向子節點的標識符和該子節點的外接矩形組成。葉子節點則存儲每個對象需要的數據，一般是一個外接矩形和指向數據的標識符。如果是點數據，葉子節點只需要存儲這些點本身。如果是多邊形數據（一般數據量很大的多邊形需要額外存儲），一般的做法是在葉子節點中存儲多邊形的最小外接矩形和指向這個多邊形的數據的標識符。

搜尋

R樹的搜尋操作很簡單，跟B樹上的搜尋十分相似。它返回的結果是所有符合查找信息的記錄條目。而輸入是不僅僅是一個範圍了，它更可以看成是一個空間中的矩形。也就是說，輸入的是一個搜尋矩形。

先給出偽代碼：

Function：Search

描述：假設T為一棵R樹的根結點，查找所有搜尋矩形S覆蓋的記錄條目。

S1:[查找子樹]如果T是非葉子結點，如果T所對應的矩形與S有重合，那么檢查所有T中存儲的條目，對於所有這些條目，使用Search操作作用在每一個條目所指向的子樹的根結點上（即T結點的孩子結點）。

S2:[查找葉子結點]如果T是葉子結點，如果T所對應的矩形與S有重合，那么直接檢查S所指向的所有記錄條目。返回符合條件的記錄。

插入

R樹的插入操作也同B樹的插入操作類似。當新的數據記錄需要被添加入葉子結點時，若葉子結點溢出，那么我們需要對葉子結點進行分裂操作。顯然，葉子結點的插入操作會比搜尋操作要複雜。插入操作需要一些輔助方法才能夠完成。

來看一下偽代碼：

Function：Insert

描述：將新的記錄條目E插入給定的R樹中。

I1：[為新記錄找到合適插入的葉子結點]開始ChooseLeaf方法選擇葉子結點L以放置記錄E。

I2：[添加新記錄至葉子結點]如果L有足夠的空間來放置新的記錄條目，則向L中添加E。如果沒有足夠的空間，則進行SplitNode方法以獲得兩個結點L與LL，這兩個結點包含了所有原來葉子結點L中的條目與新條目E。

I3：[將變換向上傳遞]開始對結點L進行AdjustTree操作，如果進行了分裂操作，那么同時需要對LL進行AdjustTree操作。

I4：[對樹進行增高操作]如果結點分裂，且該分裂向上傳播導致了根結點的分裂，那么需要創建一個新的根結點，並且讓它的兩個孩子結點分別為原來那個根結點分裂後的兩個結點。

Function：ChooseLeaf

描述：選擇葉子結點以放置新條目E。

CL1：[Initialize]設定N為根結點。

CL2：[葉子結點的檢查]如果N為葉子結點，則直接返回N。

CL3：[選擇子樹]如果N不是葉子結點，則遍歷N中的結點，找出添加E.I時擴張最小的結點，並把該結點定義為F。如果有多個這樣的結點，那么選擇面積最小的結點。

CL4：[下降至葉子結點]將N設為F，從CL2開始重複操作。

Function：AdjustTree

描述：葉子結點的改變向上傳遞至根結點以改變各個矩陣。在傳遞變換的過程中可能會產生結點的分裂。

AT1：[初始化]將N設為L。

AT2：[檢驗是否完成]如果N為根結點，則停止操作。

AT3：[調整父結點條目的最小邊界矩形]設P為N的父節點，E_N為指向在父節點P中指向N的條目。調整EN.I以保證所有在N中的矩形都被恰好包圍。

AT4：[向上傳遞結點分裂]如果N有一個剛剛被分裂產生的結點NN，則創建一個指向NN的條目E_NN。如果P有空間來存放E_NN，則將E_NN添加到P中。如果沒有，則對P進行SplitNode操作以得到P和PP。

AT5：[升高至下一級]如果N等於L且發生了分裂，則把NN置為PP。從AT2開始重複操作。

刪除

R樹的刪除操作與B樹的刪除操作會有所不同，不過同B樹一樣，會涉及到壓縮等操作。相信讀者看完以下的偽代碼之後會有所體會。R樹的刪除同樣是比較複雜的，需要用到一些輔助函式來完成整個操作。

偽代碼如下：

Function：Delete

描述：將一條記錄E從指定的R樹中刪除。

D1：[找到含有記錄的葉子結點]使用FindLeaf方法找到包含有記錄E的葉子結點L。如果搜尋失敗，則直接終止。

D2：[刪除記錄]將E從L中刪除。

D3：[傳遞記錄]對L使用CondenseTree操作

D4：[縮減樹]當經過以上調整後，如果根結點只包含有一個孩子結點，則將這個的孩子結點設為根結點。

Function：FindLeaf

描述：根結點為T，期望找到包含有記錄E的葉子結點。

FL1：[搜尋子樹]如果T不是葉子結點，則檢查每一條T中的條目F，找出與E所對應的矩形相重合的F（不必完全覆蓋）。對於所有滿足條件的F，對其指向的孩子結點進行FindLeaf操作，直到尋找到E或者所有條目均以被檢查過。

FL2：[搜尋葉子結點以找到記錄]如果T是葉子結點，那么檢查每一個條目是否有E存在，如果有則返回T。

Function：CondenseTree

描述：L為包含有被刪除條目的葉子結點。如果L的條目數過少（小於要求的最小值m），則必須將該葉子結點L從樹中刪除。經過這一刪除操作，L中的剩餘條目必須重新插入樹中。此操作將一直重複直至到達根結點。同樣，調整在此修改樹的過程所經過的路徑上的所有結點對應的矩形大小。

CT1：[初始化]令N為L。初始化一個用於存儲被刪除結點包含的條目的鍊表Q。

CT2：[找到父條目]如果N為根結點，那么直接跳轉至CT6。否則令P為N的父結點，令E_N為P結點中存儲的指向N的條目。

CT3：[刪除下溢結點]如果N含有條目數少於m，則從P中刪除E_N，並把結點N中的條目添加入鍊表Q中。

CT4：[調整覆蓋矩形]如果N沒有被刪除，則調整E_N.I使得其對應矩形能夠恰好覆蓋N中的所有條目所對應的矩形。

CT5：[向上一層結點進行操作]令N等於P，從CT2開始重複操作。

CT6：[重新插入孤立的條目]所有在Q中的結點中的條目需要被重新插入。原來屬於葉子結點的條目可以使用Insert操作進行重新插入，而那些屬於非葉子結點的條目必須插入刪除之前所在層的結點，以確保它們所指向的子樹還處於相同的層。