資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究資料結構中的希爾伯特樹
希爾伯特R樹，一種R樹的變體，被定義為多維物件的索引，例如線、區域、3D物件或基於高維特徵的引數物件。可以將其想象為B+樹在多維物件上的擴充套件。
R樹的效能取決於對節點上的資料矩形進行聚類的演算法的質量。希爾伯特R樹實現空間填充曲線，特別是希爾伯特曲線，以便對資料矩形施加線性排序。
希爾伯特R樹有兩種型別：一種用於靜態資料庫，另一種用於動態資料庫。在這兩種情況下，都實現希爾伯特空間填充曲線以實現節點中多維物件的更好排序。這種排序必須被視為“良好”，因為它應該將“相似”的資料矩形組合在一起，以減少生成的最小邊界矩形 (MBR) 的面積和周長。打包的希爾伯特R樹適用於更新非常少或根本沒有更新的靜態資料庫。
基本思想
雖然下面的例子是針對靜態環境的，但它討論了良好R樹設計的直觀原則。這些原則對靜態和動態資料庫都適用。
Roussopoulos和Leifker提出了一種構建打包R樹的技術，該技術實現了近100%的空間利用率。
該思想是根據矩形的一個角的x或y座標對資料進行排序。對四個座標中的任何一個進行排序都會得到相同的結果。在這個討論中，點或矩形都根據矩形左下角的x座標進行排序，記為“lowx打包R樹”。掃描矩形的排序列表；將連續的矩形分配給相同的R樹葉節點，直到該節點滿為止；然後構建一個新的葉節點，並繼續掃描排序列表。因此，生成的R樹的節點將被完全打包，除了每個級別上的最後一個節點可能例外。這導致空間利用率≈100%。樹的較高層次以類似的方式構建。
希爾伯特打包演算法
(將矩形打包到R樹中)
步驟1. 計算每個資料矩形的希爾伯特值。
步驟2. 按升序希爾伯特值對資料矩形進行排序。
步驟3. /* 建立葉節點 (級別l=0) */
- 當 (還有更多矩形)
- 生成一個新的R樹節點
- 將接下來的C個矩形分配到此節點
步驟4. /* 建立更高級別的節點 (l + 1) */
- 當 (級別l上有>1個節點)
- 按升序建立時間對級別l≥0的節點進行排序
- 重複步驟3
這裡的假設是資料是靜態的，或者修改頻率很低。這是一種簡單的啟發式方法，用於構建空間利用率約為100%的R樹，同時具有良好的響應時間。
542 次瀏覽
