資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究資料結構中的R*樹
基本概念
在資料處理的情況下，R*樹被定義為R樹的一種變體，用於索引空間資訊。
R*樹的構建成本略高於標準R樹，因為資料可能需要重新插入；但生成的樹通常具有更好的查詢效能。與標準R樹相同，它可以儲存點資料和空間資料。R*樹的概念由Norbert Beckmann、Hans-Peter Kriegel、Ralf Schneider和Bernhard Seeger於1990年提出。
R*樹和R樹的區別
R*樹透過重複插入構建。這棵樹幾乎沒有重疊，從而實現了良好的查詢效能。最小化覆蓋率和重疊對於R樹的效能非常重要。在資料插入或查詢時，重疊的含義是樹的多個分支需要擴充套件（由於資料被劃分為可能重疊的區域的方式）。最小化的覆蓋率增強了剪枝效能，允許頻繁地將整個頁面排除在搜尋之外，特別是對於負範圍查詢。R*樹試圖減少兩者，實現了一系列改進的節點分裂演算法和強制重新插入節點溢位的概念。這個概念基於這樣的觀察：R樹結構對其條目插入的順序高度敏感，因此插入構建（而不是批次載入）的結構可能不是最優的。條目的刪除和重新插入允許它們在樹中“找到”一個比其實際位置更合適的位置。
演算法和複雜度
- 對於查詢和刪除操作，R*樹實現了與常規R樹類似的演算法。
- 在插入時，R*樹實現了一種組合策略。對於葉子節點，最小化重疊，而對於內部節點，最小化擴充套件和麵積。
- 在分裂時，R*樹實現了一種拓撲分裂，它根據周長選擇分裂軸，然後最小化重疊。
- 除了改進的分裂策略外，R*樹還嘗試透過將物件和子樹重新插入到樹中來跳過分裂，這受到了平衡B樹概念的啟發。
因此，最壞情況下的查詢和刪除複雜度與R樹相似。R*樹的插入策略比R樹的線性分裂策略（O(M)）複雜O(M log M)，但比頁面大小為M個物件的二次分裂策略（O(M2)）複雜度低，並且對總複雜度影響不大。總的插入複雜度仍然與R樹相當：重新插入影響樹的一個分支，因此有O(log n)次重新插入，這與對常規R樹執行劃分相當。因此，總的來說，R*樹的複雜度與常規R樹相似。
更新時間： 2020年1月8日
477 次瀏覽
廣告