R*樹

R*樹
發明時間	1990年
發明者	諾伯特·貝克曼、漢斯-彼得·克里戈爾、拉爾夫·施奈德、伯恩哈德·西格
用大O符號表示的時間複雜度
算法 平均 最差 空間 $O(n)$ $O(n)$ 搜尋 $O(\log n)$ 插入 $O(\log n)$

在數據處理中，R*樹（英語：R*-tree）是R樹的一種變體，可用來索引空間信息。R*樹的構造花費比標準R樹略高，因為數據可能需要被重新插入，但生成的樹通常能獲得更好的查詢性能。像標準R樹一樣，它能存儲點和空間數據。它在1990年由諾伯特·貝克曼（Norbert Beckmann）、漢斯-彼得·克里戈爾、拉爾夫·施奈德（Ralf Schneider）和伯恩哈德·西格（Bernhard Seeger）提出。

R*樹和R樹的不同

由反覆插入構建的R*樹 (in ELKI)。 這顆樹的重疊較少，因此有很好的查詢性能。 紅的和藍的MBRs是索引頁，綠的MBRs是葉節點。

覆蓋和重疊的最小化對於R樹的性能至關重要。重疊意味着，在數據查詢和插入時，需要擴展樹的多個分支（由於數據會被拆分到許多可能重疊的區域）。覆蓋率的最小化提高了修剪性能，允許更頻繁地從搜索中排除整個頁面，特別是負範圍查詢。

R*樹通過結合修改後的節點拆分算法和在節點溢出時強制重新插入的概念，去嘗試減少覆蓋和重疊。這是基於觀察到 R-tree 結構非常容易受到其條目插入順序的影響，因此插入構建（而不是批量加載）結構可能不是最優的。條目的刪除和重新插入可能讓它們「找到」樹中比其原始位置更合適的位置。

當一個節點溢出時，它的一部分條目會從節點中刪除並重新插入到樹中。（為了避免由後續節點溢出導致的無限級聯重新插入，在插入任何新條目時，在樹的每一級中，重新插入的例程可能只被調用一次。）這帶來了在節點中生成更多聚集良好的條目組的效果，從而減少節點覆蓋。此外，實際的節點拆分經常被推遲，導致平均節點佔用率上升。重新插入可以看作是節點溢出觸發的增量樹優化的一種方法。

性能

• 改進的啟發式拆分可以生成更矩形的分頁，因此更適合許多應用程式。
• 重插方法優化了現有樹，但增加了複雜性。
• 同時高效地支持點和空間數據。

在德國郵區數據庫上不同拆分嘗試的效果

• 
  R樹，採用Guttman二次拆分方式。
  有很多從東延伸到西的頁，它們跨越整個德國，並且頁重疊很多。這無益於那些經常只需要一個與許多切片相交的小矩形區域的大多數應用。
• 
  R樹，採用Ang-Tan線性拆分。
  儘管條形區域的延伸不像Guttman拆分那樣遠，條形切割的問題影響幾乎每一個葉頁。葉頁重疊很少，但目錄頁重疊卻很多。
• 
  R*樹拓撲拆分。
  由於R*樹嘗試最小化頁重疊，使得頁重疊非常少，並且重插進一步優化此樹，拆分策略亦儘量避免產生條形區域，因而結果頁對於通常的地圖應用有用得多。

算法和複雜性

• R*樹的查詢和刪除操作使用和常規R樹一樣的算法。
• 插入時，R*樹使用一種組合策略。對於葉節點，重疊被最小化，而對於內節點，則最小化放大和面積。
• 拆分時，R*樹使用一種拓撲拆分，根據周長選擇拆分軸，然後最小化重疊。
• 除改良的拆分策略外，R*樹還嘗試通過將對象和子樹重新插入樹中來避免拆分，這受到B樹平衡概念的啟發。

因此，最壞情況下R*樹的查詢和刪除複雜度與R樹相當。R*樹的插入策略的${\mathcal {O}}(M\log M)$比R樹線性拆分策略的複雜度高（${\mathcal {O}}(M)$），但比R樹取頁大小為$M$時的二次拆分策略（${\mathcal {O}}(M^{2})$）複雜度低，並且對總複雜度沒有太大的影響。R*樹總的插入複雜性仍與R樹相當。重插至多影響一個樹支，因此重插操作具有${\mathcal {O}}(\log n)$的複雜度，這與正規R樹的拆分操作相當。總體而言，R*樹的複雜度與正規R樹處於同一數量級。

一個完整的算法實現必須考慮諸多未在此處涉及的邊角案例與特殊情況。

外部連結

包含R*樹的庫：

• Boost.Geometry rtree documentation (C++, maybe R-tree only)
• ELKI R*-tree package documentation（頁面存檔備份，存於互聯網檔案館） (Java)
• Spatial Index Library（頁面存檔備份，存於互聯網檔案館） (C++)
• SQLite R*-tree module（頁面存檔備份，存於互聯網檔案館） (C)
• TPIE Library（頁面存檔備份，存於互聯網檔案館） (C++)
• XXL Library（頁面存檔備份，存於互聯網檔案館） (Java, maybe R-tree only)

示例代碼：

• A header-only C++ R* Tree Implementation（頁面存檔備份，存於互聯網檔案館） (probably buggy and it does not generate a R*-tree, but a freely defined (by the code author) variation of the original definition)
• A 2D R*-tree implementation (C/C++)
• R-tree Demo Applet (requires Java)（頁面存檔備份，存於互聯網檔案館）