資料庫索引的答案不是「最快的搜尋演算法」，而是「最少磁碟 I/O 的資料結構」。
為什麼不用 BST 或 Red-Black Tree？
記憶體裡的操作快到可以忽略差距，但磁碟 I/O 慢了 100,000 倍以上。
一棵 Red-Black Tree 存 1 億筆資料，樹高 ≈ 2 log₂(10⁸) ≈ 54。查一筆資料要 54 次磁碟 I/O。
B-Tree 讓每個節點存 幾百個 key，樹高只有 3–4 層——同樣 1 億筆資料，3–4 次磁碟 I/O 就找到了。
BST/Red-Black Tree：
每個節點 1 個 key → 樹高 ~54 → 54 次磁碟 I/O
B-Tree（t=500）：
每個節點 ~1000 個 key → 樹高 ~3 → 3 次磁碟 I/O
差了 18 倍的磁碟存取次數。
B-Tree 結構
每個節點存多個 key，帶多個子節點（子節點數 = key 數 + 1）。
[30, 70]
/ | \
[10,20] [40,50,60] [80,90]
t = 2（minimum degree）：
- 非根節點至少 t-1 = 1 個 key
- 非根節點最多 2t-1 = 3 個 key
- 所有葉節點在同一層（完美平衡）
實務上 t 選擇讓節點大小 ≈ 磁碟 block（通常 4KB），一個節點能放幾百個 key。
插入：先預防再插入
往下走時遇到滿節點（有 2t-1 個 key）就先分裂：把中間 key 推到父節點，節點一分為二。
滿節點 [10, 20, 30] 分裂（t=2）：
20 ← 中間 key 升上去
/ \
[10] [30]
這樣保證插入的目標節點永遠有空間，不需要分裂完再回頭修復。
B-Tree vs B+Tree
資料庫幾乎都用 B+Tree，差異在資料放哪裡：
| B-Tree | B+Tree | |
|---|---|---|
| 資料位置 | 每個節點都存資料 | 只有葉節點存資料 |
| 葉節點連結 | 無 | 有雙向鏈結 |
| 範圍查詢 | 需要回溯 | 葉節點鏈結直接掃 |
| 適用 | 隨機點查詢 | 資料庫索引（點查 + 範圍查詢） |
B+Tree 範圍查詢 SELECT * WHERE id BETWEEN 30 AND 70：
1. 找到 id=30 的葉節點（3 次磁碟 I/O）
2. 沿葉節點鏈結往右掃到 70
→ 不需要回到內部節點，非常高效
MySQL InnoDB 用 B+Tree，主鍵索引（Clustered Index）的葉節點直接存行資料；Secondary Index 的葉節點存主鍵值，查到主鍵再回表。
複雜度
| 操作 | 時間 | 磁碟 I/O |
|---|---|---|
| 搜尋 | O(t × log_t n) | O(log_t n) |
| 插入 | O(t × log_t n) | O(log_t n) |
| 刪除 | O(t × log_t n) | O(log_t n) |
t 越大，樹越矮，I/O 越少——但節點越大，一次讀進記憶體的資料也越多，需要在記憶體和磁碟 block 大小之間找平衡。
B-Tree 不是為了讓演算法複雜度更好，是為了讓磁碟少轉幾圈。