R*樹

此條目翻譯品質不佳。 (2017年12月2日) 翻譯者可能不熟悉中文或原文語言，也可能使用了機器翻譯。請協助翻譯本條目或重新編寫，並注意避免翻譯腔的問題。明顯拙劣的翻譯請改掛{{d|G13}}提交刪除。

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

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

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

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

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

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

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

因此，最壞情況下R*樹的查詢和刪除複雜度與R樹相當。R*樹的插入策略的${\displaystyle {\mathcal {O}}(M\log M)}$比R樹線性拆分策略的複雜度高（${\displaystyle {\mathcal {O}}(M)}$），但比R樹取頁大小為${\displaystyle M}$時的二次拆分策略（${\displaystyle {\mathcal {O}}(M^{2})}$）複雜度低，並且對總複雜度沒有太大的影響。R*樹總的插入複雜性仍與R樹相當。重插至多影響一個樹支，因此重插操作具有${\displaystyle {\mathcal {O}}(\log n)}$的複雜度，這與正規R樹的拆分操作相當。總體而言，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)（頁面存檔備份，存於互聯網檔案館）