R樹

維基百科，自由的百科全書
R樹
類型樹
發明時間1984年
發明者安東寧·古特曼
用大O符號表示的時間複雜度
算法 平均 最差
搜尋 [1]
一個簡單的二維矩形上的R樹的例子
用ELKI做出的三維R*樹視覺效果圖（每個立方體是一個目錄頁）

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

R樹的原理[編輯]

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

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

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

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

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

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

變體[編輯]

算法[編輯]

數據格式[編輯]

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

搜索[編輯]

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

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

插入[編輯]

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

選擇插入的子樹[編輯]

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

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

分割溢出的節點[編輯]

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

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

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

不同啟發式分割算法在美國郵政區劃數據庫上的效果圖
  • Guttman的二次分割。[2] 這張圖上有很多重疊的子樹。
    Guttman的二次分割。[2]
    這張圖上有很多重疊的子樹。
  • Guttman的線性分割。[2] 結構更加糟糕，但是構建更快。
    Guttman的線性分割。[2]
    結構更加糟糕，但是構建更快。
  • Greene's split.[11] 圖上的重疊比Guttman的策略少很多。
    Greene's split.[11] 圖上的重疊比Guttman的策略少很多。
  • Chuan-Heng Ang和T. C. Tan的線性分割算法。[13] 這個策略導致子樹變成一條一條的，在查詢時通常會很糟糕。
    Chuan-Heng Ang和T. C. Tan的線性分割算法。[13]
    這個策略導致子樹變成一條一條的，在查詢時通常會很糟糕。
  • R*樹拓撲分割。[12] 圖中的重疊顯著減少，因為R*樹試圖最小化節點重疊，並且重插入策略進一步優化了樹結構。分割算法更傾向於分割出近似正方形的節點，這在一般的地圖查詢中會有更好的性能。
    R*樹拓撲分割。[12]
    圖中的重疊顯著減少，因為R*樹試圖最小化節點重疊，並且重插入策略進一步優化了樹結構。分割算法更傾向於分割出近似正方形的節點，這在一般的地圖查詢中會有更好的性能。
  • 批量加載的R*樹 排序-拼貼-遞歸 Sort-Tile-Recursive (STR). 葉子節點完全不重疊，非葉子節點（目錄節點）只有少量重疊。這是一種非常高效的樹，但是需要在構建樹之前完全了解所有數據。
    批量加載的R*樹 排序-拼貼-遞歸 Sort-Tile-Recursive (STR).
    葉子節點完全不重疊，非葉子節點（目錄節點）只有少量重疊。這是一種非常高效的樹，但是需要在構建樹之前完全了解所有數據。
  • M樹和R樹類似，但它使用嵌套的圓型節點。 分割這種節點異常複雜，並且節點間的重疊通常也比其它算法多得多。
    M樹和R樹類似，但它使用嵌套的圓型節點。
    分割這種節點異常複雜，並且節點間的重疊通常也比其它算法多得多。

刪除[編輯]

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

批量加載[編輯]

  • X軸最近原則 – 把數據按照它們第一坐標值（X軸坐標）排序，然後按照想要的大小分割。
  • 批量Hilbert R樹 – X軸最近原則的變體。把數據按照它們的外接矩形中心點的Hilbert值排序，然後分割。不能保證節點之間沒有重疊。
  • 排序-拼貼-遞歸：Sort-Tile-Recursive (STR):[15] X軸最近原則的另一種變體，先估算需要的葉子節點數：和每個維度上需要分割的份數：。然後依次把每個維度分為等分。分割之後如果有哪一份的數據超過了條目上限就使用相同的方法繼續等分。如果是點數據，葉子節點間不會重疊。算法會拼接一些數據塊，使得所有葉子節點的數據量大致相當。
  • 優先級R樹

參見[編輯]

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

參考資料[編輯]

  1. ^ R Tree cs.sfu.ca
  2. ^ 2.0 2.1 2.2 Guttman, A. (1984).
  3. ^ Y. Manolopoulos; A. Nanopoulos; Y. Theodoridis (2006).
  4. ^ 4.0 4.1 Schubert, E.; Zimek, A.; Kriegel, H. P. (2013).
  5. ^ Roussopoulos, N.; Kelley, S.; Vincent, F. D. R. (1995).
  6. ^ Hwang, S.; Kwon, K.; Cha, S. K.; Lee, B. S. (2003).
  7. ^ Arge, L.; De Berg, M.; Haverkort, H. J.; Yi, K. (2004).
  8. ^ Brinkhoff, T.; Kriegel, H. P.; Seeger, B. (1993).
  9. ^ Achtert, E.; Böhm, C.; Kröger, P. (2006).
  10. ^ Kuan, J.; Lewis, P. (1997).
  11. ^ 11.0 11.1 Greene, D. (1989).
  12. ^ 12.0 12.1 Beckmann, N.; Kriegel, H. P.; Schneider, R.; Seeger, B. (1990).
  13. ^ 13.0 13.1 Ang, C. H.; Tan, T. C. (1997).
  14. ^ Berchtold, Stefan; Keim, Daniel A.; Kriegel, Hans-Peter (1996).
  15. ^ Leutenegger, Scott T.; Edgington, Jeffrey M.; Lopez, Mario A. (February 1997).

外部連結[編輯]

二叉樹
自平衡二叉查找樹
B樹
堆
Trie
二叉空間分割（BSP）樹
非二叉樹
空間數據分割樹
其他樹
類型
抽象類型
數組
鏈（英語：Linked data structure）
樹
圖
取自 "https://zh.wikipedia.org/w/index.php?title=R树&oldid=80443903"