R树

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

## R 樹的原理

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

跟 B 樹類似，R 樹也是平衡樹（所以所有葉子節點都在同一深度）。它把資料按（記憶體）頁儲存，是為磁碟儲存設計的（跟資料庫的做法相同）。每一頁可以儲存不超過一個上限的條目，這個上限一般用 $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\* 樹
* R + 樹
* Hilbert R 樹
* X 樹

## 演算法

### 資料格式

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

### 搜尋

輸入是一個搜尋矩形（搜尋方塊）。搜尋演算法和 B + 樹類似，從根節點開始，每個非葉子節點包含一系列外接矩形和指向對應子節點的指標，而葉子節點則包含空間物件的外接矩形以及這些空間物件（或者指向它們的指標）。對於搜尋路徑上的每個節點，遍歷其中的外接矩形，如果與搜尋方塊相交就深入對應的子節點繼續搜尋。這樣遞迴地搜尋下去，直到所有相交的矩形都被存取過為止。如果搜尋到一個葉子節點，則嘗試比較搜尋方塊與它的外接矩形和資料（如果有的話），如果該葉子節點在搜尋方塊中，則把它加入搜尋結果。

對於最鄰近搜尋這類優先級搜尋，可以查詢一個矩形或者一個點。 先把根節點加入優先佇列，然後查詢優先佇列中離查詢的矩形或者點最近的項，直到優先佇列被清空或者已經得到要求的鄰居數。從優先佇列頂端取出每個節點時先將其展開，然後把它的子節點插回優先佇列。如果取出的是子節點就直接加入搜尋結果 。這個方法可以應用於包括（地理資訊的）大圓距離在內的多種距離度量方式。

### 插入

插入節點時，演算法從樹的根節點開始遞迴地向下遍歷。檢查當前節點中所有外接矩形，並啟發式地選擇在哪個子節點中插入（例如選擇插入後外接矩形擴張最小的那個子節點），然後進入選擇的那個子節點繼續檢查，直到到達葉子節點。滿的葉子節點應該在插入之前分割，所以插入時到達的葉子節點一定有空位來寫資料。由於把整棵樹遍歷一遍代價太大，在分割葉子節點時應該使用啟發式演算法。把新分割的節點添加進上一層節點，如果這個操作填滿了上一層，就繼續分割，直到到達根節點。如果跟節點也被填滿，就分割根節點並建立一個新的根節點，這樣樹就多了一層。

#### 選擇插入的子樹

插入演算法在樹的每一層都要決定把新的資料插入到哪個子樹中。如果只有一個外接矩形包含新資料，那麼很容易選擇。但如果有多個外接矩形包含新資料，或者所有外界矩形都不包含新資料，那麼選擇演算法會極大地影響 R 樹的效能。

經典 R 樹的實現會把資料插入到外接矩形需要增長面積最小的那個子樹。而更進一步的 R\* 樹則使用了一種混合的啟發式演算法。如果需要選擇的子樹是葉子節點，它會選擇造成最小重疊的子樹，如果有多個選擇不分上下，則選擇外接矩形增長最小的子樹，再不分上下則選擇面積最小的子樹。如果需要選擇的子樹不是葉子節點，演算法和 R 樹類似，但在不分上下時選擇面積較小的子樹。比 R 樹更少的重疊是 R\* 樹對 R 樹的主要優勢之一（這也有 R\* 樹上應用的其它啟發式演算法的原因，並不僅僅因為選擇子樹演算法的不同）。

#### 分割溢位的節點

因為有指數多種方式來把一個節點中所有物件分割到兩個節點，我們需要使用啟發式演算法來尋找最佳分割。在經典 R 樹中，Guttman 提出了二次分割和線性分割兩種啟發式演算法。二次分割演算法在節點中尋找放在同一個節點中最糟糕的兩個物件，把它們作為兩個新節點的初始資料。然後把資料集中對其中一個新節點有最強偏向的資料（外接矩形最小面積增長）分給這個節點，直到所有資料都被分配（節點中資料多於最小條目數）。

還有其它的分割策略，例如 Greene's Split，R\* 樹啟發式分割策略（它也試圖儘量減小重疊，但同時也偏向正方形的節點）以及 Chuan-Heng Ang 和 T. C. Tan 提出的線性分割演算法 （這種演算法會產生形狀很不規則的矩形，在很多現實資料分布以及使用搜尋方塊時效率較低）。R\* 樹不僅使用了更進階的啟發式分割，而且還通過重新插入一些數值來試圖避免分割節點（這跟 B 樹平衡溢位節點的策略類似）。這個方法被證明還可以減少重疊，從而進一步提高 R 樹效能。

最後，X 樹（可以被視為 R\* 樹的變體）也決定避免分割節點。當 X 樹找不到一個好的分割方式（尤其在高維資料的情況下）時會構建一個所謂的「超節點」來放置溢位的資料。

### 刪除

從一個節點中刪除一條資料可能會導致演算法需要更新它的父節點的外接矩形。但是當一個節點中的資料不足時，它不會和兄弟節點重新平衡。這個節點會被直接刪除，它的子節點（可能是子樹，不一定是葉子節點）會被重新插入。如果在這個過程中根節點只剩下一個子節點，可以把根節點刪除，樹的高度降低。

### 批次載入

* X 軸最近原則 – 把資料按照它們第一坐標值（X 軸坐標）排序，然後按照想要的大小分割。
* 批次 Hilbert R 樹 – X 軸最近原則的變體。把資料按照它們的外接矩形中心點的 Hilbert 值排序，然後分割。不能保證節點之間沒有重疊。
* 排序 - 拼貼 - 遞迴：Sort-Tile-Recursive (STR): X 軸最近原則的另一種變體，先估算需要的葉子節點數： $l=\lceil {\text{对 象 数 量 }}/{\text{节 点 容 量 }}\rceil $ 和每個維度上需要分割的份數： $s=\lceil l^{1/d}\rceil $ 。然後依次把每個維度分為 $s$ 等分。分割之後如果有哪一份的資料超過了條目上限就使用相同的方法繼續等分。如果是點資料，葉子節點間不會重疊。演算法會拼接一些資料塊，使得所有葉子節點的資料量大致相當。
* 優先級 R 樹

## 參見

* 線段樹
* 區間樹 – 一維資料集（通常是時間資料）上的退化的 R 樹。
* Bounding volume hierarchy
* Spatial index
* GiST

## 參考資料

## 外部連結

* R 樹的代碼： C & C++（頁面存檔備份，存於網際網路檔案館）, Java（頁面存檔備份，存於網際網路檔案館）, Java applet（頁面存檔備份，存於網際網路檔案館）, Common Lisp（頁面存檔備份，存於網際網路檔案館）, Python（頁面存檔備份，存於網際網路檔案館）, Scala（頁面存檔備份，存於網際網路檔案館）, Javascript（頁面存檔備份，存於網際網路檔案館）, Javascript (including interactive demo)（頁面存檔備份，存於網際網路檔案館）
* Boost.Geometry library containing R-tree implementation (various splitting algorithms)