資料庫索引的答案不是「最快的搜尋演算法」，而是「最少磁碟 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。
搜尋：節點內線性掃，節點間往下跳
搜尋跟二元樹很像，只是每一層不再是「左 or 右」二選一，而是在節點的一排 key 裡找對應區間：
[30, 70] 找 50
↓ 30 < 50 < 70 → 落在中間那段，進中間子節點
[40, 50, 60] 找到 50 ✓在節點內找「第一個 ≥ 目標」的 key：命中就回傳、落到葉節點還沒中就是不存在、否則遞迴進對應子節點。節點內那排 key 通常直接線性掃就好——反正一個節點只有幾百個 key、又已經讀進記憶體，記憶體裡掃幾百次的成本跟一次磁碟 I/O 比起來根本是零頭。真正貴的是「往下走一層 = 一次磁碟 I/O」，所以樹高才是效能的命脈。
插入：先預防再插入
往下走時遇到滿節點（有 2t-1 個 key）就先分裂：把中間 key 推到父節點，節點一分為二。
滿節點 [10, 20, 30] 分裂（t=2）：
20 ← 中間 key 升上去
/ \
[10] [30]這樣保證插入的目標節點永遠有空間，不需要分裂完再回頭修復。
寫成 code 就是一路往下遞迴、下探前先看子節點滿沒滿：
// 前提：node 目前保證未滿，往下走前先把「即將進入的滿子節點」分裂掉
private void insertNonFull(Node node, int key) {
int i = node.n - 1;
if (node.leaf) { // 到葉節點，直接插
while (i >= 0 && key < node.keys[i]) {
node.keys[i + 1] = node.keys[i--]; // 後移騰位
}
node.keys[i + 1] = key;
node.n++;
} else {
while (i >= 0 && key < node.keys[i]) i--;
i++;
if (node.children[i].n == 2 * t - 1) { // 子節點滿了
splitChild(node, i); // 先分裂，中間 key 升上來
if (key > node.keys[i]) i++; // 升上來的 key 可能改變去向
}
insertNonFull(node.children[i], key);
}
}「下探前先分裂」是 B-Tree 插入最反直覺、也最關鍵的一手——它讓整個插入是單趟往下（one pass down），不需要像 AVL 那樣插完再回溯修復。
刪除：借 key 或合併
刪除比插入囉嗦，因為要處理反方向的問題：節點 key 太少（低於 t-1 個）就違反了 B-Tree 的下限。修法有兩招——跟兄弟「借」一個 key，或跟兄弟「合併」成一個節點。
| 情況 | 處理 |
|---|---|
| key 在葉節點 | 直接刪 |
| key 在內部節點 | 用前驅或後繼 key 頂替，再去葉節點刪掉那個頂替者 |
| 刪完子節點 key 不足（< t-1） | 先向左右兄弟借一個；兄弟也不夠借就合併兩個子節點 |
插入是「怕滿、先分裂」，刪除是「怕空、借或合併」——一脹一縮，兩邊都在維持「每個節點 key 數落在 [t-1, 2t-1]」這條區間，這正是 B-Tree 永遠完美平衡的來源。
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 插入與分裂動畫 — 連續插入 key，看滿節點怎麼把中間 key 往上推、一分為二，感受「所有葉節點永遠在同一層」是怎麼被撐出來的。
B-Tree 不是為了讓演算法複雜度更好，是為了讓磁碟少轉幾圈。
接下來往哪走
- HyperLogLog 用 1.5 KB 計算十億個不同用戶 — 下一篇：從索引結構切到機率型資料結構
- BRIN 和什麼時候索引反而更慢 — B+Tree 索引在資料庫實務上的設計取捨與踩坑點
- Red-Black Tree 紅黑樹 — 同樣是平衡樹，in-memory 場景該用的是這種