跳至內容

R*樹

維基百科,自由的百科全書
R*樹
發明時間1990年
發明者諾伯特·貝克曼、漢斯-彼得·克里戈爾、拉爾夫·施奈德、伯恩哈德·西格
大O符號表示的時間複雜度
算法 平均 最差
空間
搜尋
插入

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

R*樹和R樹的不同

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

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

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

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

性能

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

算法和複雜性

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

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

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

參考資料

  1. ^ 1.0 1.1 Beckmann, N.; Kriegel, H. P.; Schneider, R.; Seeger, B. Proceedings of the 1990 ACM SIGMOD international conference on Management of data - SIGMOD '90 (PDF): 322. 1990 [2018-04-03]. ISBN 0897913655. doi:10.1145/93597.98741. (原始內容存檔 (PDF)於2018-04-17).  |chapter=被忽略 (幫助)
  2. ^ Antonin Guttman, Antonin Guttman. R-trees: a dynamic index structure for spatial searching, R-trees: a dynamic index structure for spatial searching. ACM SIGMOD Record. 1984-06-18, 14 (2): 47, 47–57, 57 [2018-04-02]. ISSN 0163-5808. doi:10.1145/602259.602266. [永久失效連結]
  3. ^ C. H. Ang, T. C. Tan. New linear node splitting algorithm for R-trees. Springer, Berlin, Heidelberg: 337–349. 1997-07-15 [2018-04-02]. ISBN 3540632387. doi:10.1007/3-540-63238-7_38. (原始內容存檔於2018-06-06) (英語). 

外部連結

包含R*樹的庫:

示例代碼: