sql5 4.0.2

# B+Tree - 資料結構理論

`src/btree/`

## B+Tree 定義

B+Tree 是一種自平衡的樹狀資料結構，專為區塊儲存設計，廣泛用於資料庫索引。

```
      [5 | 10 | 15]
     /    |     \
  [1-4] [6-9] [11-14] [16-20]
```

## 與 B-Tree 的差異

| 特性 | B-Tree | B+Tree |
|------|--------|--------|
| 資料儲存 | 內部節點 + 葉節點 | 仅葉節點 |
| 葉節點連結 | 否 | 是（雙向鏈表） |
| 查詢穩定性 | O(log n) ~ O(n) | O(log n) 穩定 |
| 範圍查詢 | 需回溯 | 鏈表遍歷 |

## B+Tree 的特性

### 節點容量
- 每節點可容納多個 key（通常為數十到數百）
- 減少樹的高度

### 平衡性
- 所有葉節點深度相同
- 插入/刪除時通過分裂/合併維持平衡

## 查詢復雜度

```
高度 h ≈ log_⌈m/2⌉ (N/m)

其中：
- m = 每節點最大 key 數
- N = 總 key 數
```

典型查詢為 2-3 次磁碟讀取（樹深度 2-3）。

## 插入演算法

1. 找到應插入的葉節點
2. 若節點未滿，直接插入並排序
3. 若節點已滿，分裂為兩節點
4. 向上更新父節點 key

## 刪除演算法

1. 找到並刪除葉節點中的 key
2. 若節點 key 數過少，借用相鄰節點的 key
3. 或與相鄰節點合併
4. 向上調整

## 磁碟友善性

| 設計 | 原因 |
|------|------|
| 大節點 | 減少磁碟讀取次數 |
| 節點對齊 | 符合磁碟區塊大小 |
| 順序訪問 | 葉節點鏈表支援區間掃描 |

## 理論參考

- Bayer & McCreight, "Organization and Maintenance of Large Ordered Indices" (1972)
- Comer, "The Ubiquitous B-Tree"
- 資料庫系統概念（第 6 版）第 10 章