# 【R-Tree：高效空間資料索引結構】

R-Tree 是一種專為處理多維空間數據（例如地理座標）設計的樹狀數據結構。它類似於 B 樹，但將搜尋範圍從一維區間拓展至多維空間，是高維度資料索引的理想選擇。其是二維空間數據，如地理座標）設計的樹形數據結構

<br>

## 🌲 R-Tree 的基本運作流程

### 層次結構：
- **Level 1**：葉子節點層，儲存實際數據點。
- **Level-h**：根節點層，包含整棵樹的最小邊界矩形（MBR，Minimum Bounding Rectangle）。

### 節點規則：
- 除根節點外，每個節點包含 m 至 M 個條目，m 通常為 M 的一半。
- 所有葉子節點都在同一層，因此 R-Tree 是平衡樹。
- 非葉節點的條目形式為 `(I, child_pointer)`，I 是一個 MBR，child_pointer 指向子節點。

### 最小邊界矩形 (MBR)：
- 在 2D 空間中，MBR 是一個矩形，包含其子節點的所有空間數據。
- 在 3D 空間中，MBR 變為立方體，覆蓋子節點的所有數據。

下面建構一棵 R樹。如下左圖，理論上，點可以任意組合成葉節點，只要 MBR 包含它子樹中的所有點。特別是 MBRMBR 可以重疊。下面右圖是另一個組合建立的 R樹。



一般分組的原則就是最小化每個MBR 矩形，這樣查詢的時候發生的相交情況會越少，查詢的分支就越少，查詢效率越高。

<br>

## ⚙️ R-Tree 的核心操作
### 🔍 1. 插入操作
- 過程：
1. 從根節點開始，選擇擴張最小的 MBR 子節點進行插入。
2. 若目標節點已滿，則進行節點分裂，生成兩個新的 MBR，並向上更新父節點的邊界。
3. 若根節點也分裂，會生成新的根節點，確保樹的平衡性。

- 範例：插入四個城市（北京、上海、廣州、深圳）：
1. 插入前兩個城市至根節點。
2. 插入廣州，若節點未滿，直接插入。
3. 插入深圳時若節點滿員，將其分裂為兩個節點：北方城市（北京、上海）、南方城市（廣州、深圳）

### 📍 2. 查詢操作
- 過程：
1. 從根節點開始，檢查每個子節點的 MBR 是否與查詢區域重疊。
2. 若有重疊，深入子節點重複此操作。
3. 搜索到葉子節點，返回所有重疊的數據。

- 範例：查詢長江以南城市：
1. 從根節點範圍搜尋。
2. 搜索南方城市節點（廣州、深圳）。
3. 北方節點（北京、上海）無需檢查。

### ❌ 3. 刪除操作
- 過程：
1. 定位包含要刪除數據的葉節點。
2. 刪除後檢查節點是否低於最小條目數，若是，合併或重平衡相鄰節點。
3. 更新 MBR，維持樹的平衡性。

- 範例：刪除廣州：
1. 刪除廣州數據，檢查葉節點條目數。
2. 若剩下深圳，將其合併至其他節點，重新更新父節點的邊界。

<br>

## 🏗️ R-Tree 的結構特點
1. **分層結構**：根節點位於最上層，葉節點包含實際數據。

2. **節點填充因子**：為了確保查詢效率，節點內數據數量需符合設定的比例，避免樹的高度過高或節點分裂過度。

3. **超矩形分割**：透過最小邊界矩形（MBR，Minimum Bounding Rectangle）或最小面積包圍盒（Min-Area Bounding Box）分割空間，降低重疊情況，提高查詢效率。

<br>

## 🔍 R-Tree 的應用領域
- **地理資訊系統（GIS）**：快速檢索地理空間數據（例如地圖服務中的地標搜尋）。
- **空間數據庫**：管理大量多維空間數據（例如建築、衛星影像、城市數據）。
- 遊**戲開發**：碰撞檢測、場景分割。
- **計算機視覺**：快速查找與影像特徵匹配的區域。
- **物聯網（IoT）**：追蹤和搜尋空間中的移動物體（例如自動駕駛路徑搜尋）。

## 📘 研讀指南
1. **R 樹解決了什麼問題，為什麼傳統的索引方法不適用？**
- R 樹主要解決了高效索引**多維空間數據**的問題，這些數據通常具有非零大小（例如地圖上的城市或圖像中的物體）。
- 傳統索引方法如 **Hash Table** 和 **B-Tree** 只適用於一維數據，對於**範圍搜尋**和多維空間數據（例如在地圖中搜尋半徑 10 公里的所有餐廳）效率低下。

2. **簡要描述 R 樹的結構。包括葉節點和非葉節點中存儲的資訊。**
- **葉節點**：儲存實際數據物件的索引記錄，每條記錄包含：
1. 一個邊界框（n 維矩形），定義物件的空間範圍。
2. 指向物件實體的指標（例如城市名稱或物件 ID）。
- **非葉節點**：儲存指向下一層節點的指針，並包含一個覆蓋所有子節點矩形的最小邊界矩形（MBR）。
1. 例如，若某非葉節點下的兩個子節點分別代表「北方城市」和「南方城市」，則該節點的 MBR 會覆蓋所有這些城市的範圍。

3. **R 樹的 "m" 和 "M" 參數代表什麼？它們如何影響樹的結構和性能？**
- m：節點中條目的**最小數量**（通常為 `M / 2`）。
- M：節點中條目的**最大數量**，由節點大小決定。
- 影響：
1. 較大的 m 值：提高節點利用率、減少樹的高度，但在刪除記錄時可能需要更多重新插入。
2. 較大的 M 值：能容納更多資料，減少分裂頻率，但會增加每次搜尋需要檢查的條目數量。

4. **在 R 樹中進行空間搜索時，如何決定要搜尋哪些子樹？**
- 搜尋時，從根節點開始檢查每個子節點的 MBR 是否與搜尋矩形重疊。
- 例如，若搜尋「半徑 10 公里內的餐廳」，只有與該搜尋範圍重疊的節點才需要繼續探索，這樣能避免不必要的遍歷，提升效率。

5. **描述在 R 樹中插入新記錄的過程。**
- ChooseLeaf 演算法：
1. 從根節點開始，找到最小擴展能夠容納新記錄的 MBR。
2. 在葉節點插入新記錄，若節點已滿則進行分裂。
3. 使用 AdjustTree 向上更新父節點，保持樹的平衡。

6. **解釋 "ChooseLeaf" 算法的目的和過程。**
- 目的：找到最合適插入新記錄的葉節點，減少未來搜尋時的冗餘路徑。
- 過程：優先選擇需要最少擴展的矩形，確保插入後空間重疊最小化。

7. **說明在 R 樹中刪除記錄的過程。**
- 使用 **FindLeaf** 找到包含該記錄的葉節點，並刪除記錄。
- 使用 **CondenseTree** 向上更新節點，若條目數過少，則可能重新插入其他節點以維持平衡。

8. **解釋 "CondenseTree" 算法的目的。它與 B 樹的合併操作有何不同？**
- 目的：保持樹的平衡並最小化空間浪費。
- 不同於 B 樹的合併，R 樹會重新插入條目較少的節點，而不是直接合併。
- 優點：這樣可以避免生成過多冗餘的矩形範圍。

9. **在節點分裂算法中，為什麼要最小化分裂後覆蓋矩形的總面積？**
- 總面積越小，未來進行空間搜尋時需要檢查的節點數就越少。
- 範例：如果一個城市分裂後的兩個矩形範圍過大，將來搜尋「北方城市」時，可能會誤檢查到不相關的「南方城市」區域。

10. **簡述文章中提到的三種節點分裂算法（詳盡、二次成本、線性成本），並說明它們的複雜度。**
- 詳盡算法（Exhaustive）：測試所有可能分裂組合，找出最優分裂方式，複雜度高，適合小規模數據。
- 二次成本算法（Quadratic Cost）：選擇最浪費面積的兩個條目作為起點，並根據增量面積分配其他條目，效率較高。
- 線性成本算法（Linear Cost）：基於條目的邊界極值進行快速分裂，複雜度最低，適合大規模數據。

## 術語表

| 名詞 | 簡介 |
| :--: | :-- |
| R 樹 (R-tree) | 一種用於索引多維空間資料的樹狀資料結構，適用於地理資訊系統（GIS）和電腦輔助設計（CAD）。 |
| 邊界框 (Bounding Box) | 包圍單個資料物件的最小矩形。用於描述物件在空間中的最小矩形範圍，常用於快速範圍搜尋。 |
| 節點分裂 (Node Splitting) | 當節點已滿時，將節點中的條目分成兩個節點的過程，以維持樹的結構。 |
| 覆蓋矩形 (Covering Rectangle) | 包圍一個子節點內所有邊界框的最小矩形。包圍節點中所有矩形的最小矩形，用於非葉節點中表示子樹的空間範圍。 |
| 搜尋矩形 (Search Rectangle) | 查詢時用於篩選的矩形，將會檢查與其重疊的節點。 |
| 高度平衡樹 (Height-Balanced Tree) | 保持所有葉節點在同一層級，確保搜尋操作的時間複雜度保持穩定。 |
| 空間資料 (Spatial Data) | 具有空間屬性和範圍的資料，例如地圖上的城市或建築物。 |
| 索引記錄 (Index Record) | 葉節點中存儲的條目，包含邊界框和對應的物件指針。 |
| m (最小條目數) | 節點中必須包含的最少條目數，影響樹的平衡性。 |
| M (最大條目數) | 節點中可以包含的最大條目數，取決於節點的大小與結構設計。 |