B-Tree 把磁碟切成固定大小的頁（page），組成一棵就地更新的平衡樹。它是關聯式資料庫四十年來的預設索引結構，核心賣點是穩定、可預測的讀延遲。
🧠 Intuition
TIP
把 B-Tree 想成一本字典的目錄樹：每一頁是一張紙，紙上寫著「key 落在哪個區間，就翻到哪一頁」。讀任何一筆都從根頁往下翻固定幾層，所以延遲穩定；改任何一筆都是「翻到那一頁、原地塗改」，所以寫是隨機 I/O。
- 固定大小頁：磁碟以頁（通常 4KB~16KB）為讀寫單位，每頁存一批有序 key 與指向子頁的指標；頁大小對齊底層 block，減少讀放大。
- 平衡樹結構：所有葉頁都在同一深度，樹高 = O(log n)。分支因子（一頁能塞的 key 數）很大，所以即使上億筆資料，樹高也只有 3~4 層。
- 就地更新（update-in-place）：找到 key 所在的頁，直接覆寫該頁的位元組；這跟 LSM 的「只追加、背景合併」是哲學上的對立面。
⚖️ Tradeoffs
頁分裂與合併 (Page Split & Merge)
- 插入時若目標葉頁已滿，把頁分裂成兩頁，並在父頁插入一個新的分隔 key；分裂可能向上遞迴，極端時長高一層。
- 刪除使頁過空時可合併相鄰頁（多數實作偷懶，靠後續維護或 vacuum 處理，不即時合併）。
- 代價：分裂是隨機寫的放大來源，且會在頁內留下空隙（fill factor < 100%），造成空間碎片。
WAL / redo log — 崩潰安全的基石
- 就地覆寫一頁不是原子操作：寫到一半斷電 → 頁損毀（torn page）。
- 解法：改頁之前先把變更順序寫進 WAL（write-ahead log / redo log），崩潰後重放 WAL 即可把頁修回一致狀態。
- 代價：一次邏輯寫 = WAL 一次 + 頁本身一次，這是 B-Tree 寫放大的固定來源。
讀延遲為何穩定
- 讀一筆 = 從根往下走固定 O(log n) 次頁存取，路徑長度與資料量幾乎無關。
- 不像 LSM 要查 memtable + 多個 SSTable 層、靠 Bloom filter 救；B-Tree 讀路徑單一，p99 容易壓住。
- 上層頁通常常駐 buffer pool（記憶體），實際打到磁碟的只有最後一兩跳。
並發控制：latch 與鎖耦合 (latch crabbing)
- 多執行緒同時改樹，需對頁加 latch（短期記憶體鎖）保護結構完整性。
- 經典手法是 latch crabbing／coupling：往下走時先鎖子頁、確認安全再放父頁，像螃蟹交替伸爪。
- 代價：高並發寫入時，靠近根的頁容易成為 latch 競爭熱點。
🔑 Takeaways
- B-Tree = 固定頁 + 平衡樹 + 就地更新，分支因子大讓樹只有 3~4 層，讀路徑固定、延遲穩定。
- 頁分裂/合併維持平衡，但帶來隨機寫放大與頁內碎片（fill factor）。
- WAL/redo log 是就地更新的崩潰安全前提，也是寫放大的固定來源。
- 適合讀重、要穩定 p99 的 OLTP 負載：PostgreSQL、MySQL InnoDB。
2026-07-01
- Q: 既然 WAL 已經把每次變更順序寫一份了，為什麼不乾脆只靠 WAL、不要就地改頁？
- A: 那其實就快變成 LSM 的思路了。只靠 log 的問題是讀要回放整段 log 才能重建狀態，讀會爆炸；B-Tree 的 WAL 只是「短期的崩潰保險」，正本永遠是頁本身，重放後就可丟棄（checkpoint 截斷）。LSM 則是把「log 即資料」推到底、再用 compaction 與 Bloom filter 把讀救回來——兩者是同一條光譜的兩端。