B-Tree 內部機制#
02-database/02 索引 講過 B+ Tree 的「對外行為」── 查找對數級、覆蓋索引、索引下推。但「為什麼一次寫入會牽動好幾層、崩潰後憑什麼還能救回來」是引擎內部的事。本章補的就是這層：頁分裂與合併的具體步驟、WAL 的追寫順序與原子性、崩潰恢復的 redo/undo 三階段，以及 latch 怎麼讓多執行緒安全地動同一棵樹。
隔離級別、MVCC、間隙鎖在 03 賬戶事務與隔離級別 與 02-database/03 已談。這裡聚焦物理結構的變更與恢復，不重述邏輯並發控制。
頁分裂：寫入如何牽動整棵樹#
B-Tree 是就地更新（in-place update）結構，節點即磁碟頁面（page，通常 4~16 KB）。插入先從根遍歷到葉，找到目標葉節點後就地寫入。當目標頁空間不足（overflow），就得分裂。
觸發條件對葉與內部節點不同：
| 節點類型 | 容量上限 | 溢出條件 |
|---|---|---|
| 葉節點 | N 個鍵值對 | 再插一個會超過 N |
| 內部節點 | N + 1 個子指標 | 再插一個指標會超過 N + 1 |
分裂的四個步驟：
- 分配一個新頁
- 把分裂頁的一半元素搬到新頁（在分裂點 / midpoint 切開）
- 把新元素插入到正確的一邊（小於提升鍵 ➡️ 留原頁，否則 ➡️ 新頁）
- 在父節點插入一個分隔鍵（separator key）+ 指向新頁的指標 ── 這個鍵被「提升（promoted）」上去
葉節點與內部節點分裂的差異，在於提升鍵的命運：
- 葉節點分裂：中間鍵複製一份提升到父節點（葉層仍保留該鍵，因為值在葉）
- 內部節點分裂：中間鍵移動到父節點（內部節點只存導引鍵，不留副本）
連鎖分裂與樹長高#
如果父節點本來就快滿，提升一個分隔鍵又讓父節點溢出 ➡️ 父節點也分裂 ➡️ 再往上提升。這就是連鎖分裂（cascading split），最遠可一路傳播到根。
stateDiagram-v2
[*] --> 定位葉節點: 從根遍歷 + 二元搜尋
定位葉節點 --> 葉有空間: 佔用率 < 100%
定位葉節點 --> 葉溢出: 已滿
葉有空間 --> 就地插入
就地插入 --> [*]
葉溢出 --> 分裂葉: 分配新頁 + 搬一半
分裂葉 --> 提升分隔鍵: 寫入父節點
提升分隔鍵 --> 父有空間
提升分隔鍵 --> 父溢出
父有空間 --> [*]
父溢出 --> 分裂內部: 連鎖向上
分裂內部 --> 根分裂: 一路到根
根分裂 --> 樹長高: 建新根，h + 1
樹長高 --> [*]關鍵觀察：B-Tree 只在根分裂時才長高，且新根剛建立時只有一個分隔鍵、兩個子指標。所以根節點是「最後才分裂、最常被讀」的節點 ── 這個特性在 latch 設計時會被利用（見下）。
向上找父節點需要知道遍歷路徑，兩種做法：
- 父節點指標：節點存指向父的指標，分裂/合併時更新
- 麵包屑（breadcrumbs）：遍歷時用堆疊記錄走過的節點與 cell 索引，分裂時從堆疊頂端彈出定位父節點（PostgreSQL 的
BTStack，純記憶體不落盤）
合併與借位：處理低佔用頁#
刪除是分裂的反操作。移除鍵值對後，若節點佔用率低於閾值就下溢（underflow），需要處理：
合併（merge）條件：
| 節點類型 | 合併條件（兩相鄰節點） |
|---|---|
| 葉節點 | 鍵值對總和 <= N |
| 內部節點 | 指標總和 <= N + 1 |
合併步驟：把右節點所有元素搬進左節點 ➡️ 從父節點移除右節點指標（內部節點合併時把分隔鍵降級 demote 下來）➡️ 釋放右節點。合併同樣可遞迴傳播到根，這時樹會變矮。
但若兩個相鄰節點加起來放不下單一頁，就不合併，改重新平衡（rebalancing）/ 借位：在相鄰節點間重新分配鍵，順帶更新父節點的分隔鍵。延遲分裂與合併、改用借位，能提高佔用率、減少結構抖動（SQLite 的 balance-siblings、B*-Tree 把兩滿節點拆成三個各填約 2/3）。
50% 佔用率下界與預留空間#
B-Tree 是從底向上生長的：葉節點滿了才分裂，分裂後兩頁各約半滿。所以最壞情況下，剛分裂完的頁佔用率只有約 50%，這是 B-Tree 的空間利用率下界。
這正是 B-Tree 與 LSM 在空間放大上的根本差異：
- B-Tree 預留空間給未來插入（半滿頁可以繼續塞），代價是磁碟利用率可能只有 50~70%
- 例外：**批次載入（bulk loading）**已排序資料時可由下而上建樹、每頁填滿，因為之後不打算原地改 ── 不可變 B-Tree（如 LSM 內部的索引）就用這招達到 100% 佔用
WAL：先寫日誌的追寫順序與原子性#
頁分裂改的可能是好幾個頁（葉 + 父 + 新頁），這些寫入不可能在磁碟上一瞬間原子完成。崩潰可能停在中間，留下一棵壞掉的樹。**預寫式日誌（Write-Ahead Log, WAL）**解決這個問題。
核心鐵律（write-ahead 的字面意思）：
每個修改資料庫狀態的操作，必須在相關頁面內容被改之前，先把對應日誌記錄持久化到磁碟。 WAL 是 append-only、寫入後不可變，所有寫入都是順序 I/O。 一筆事務在它的 commit 記錄的 LSN 被 force 到磁碟之前，不算已提交。
WAL 與頁快取（page cache / buffer pool）的協作時序：
sequenceDiagram
participant App as 應用
participant Log as WAL（磁碟）
participant Cache as 頁快取（記憶體）
participant Disk as 資料檔（磁碟）
App->>Log: 1. 追寫 redo/undo 記錄（含 LSN）
Log-->>App: fsync 完成（落盤）
App->>Cache: 2. 修改快取頁（標記 dirty）
App->>Log: 3. 追寫 COMMIT 記錄
Log-->>App: fsync COMMIT（此刻才算已提交）
Note over Cache,Disk: 髒頁稍後由背景 writer / checkpoint 非同步刷回
Cache-->>Disk: 4. flush dirty pages（與提交解耦）每筆日誌記錄帶單調遞增的 LSN（Log Sequence Number）。日誌記錄先進日誌緩衝區，由 force 操作刷到磁碟。checkpoint 標記「到此為止的記錄都已持久化」，已刷回快取頁對應的日誌段才能丟棄，大幅縮短重啟恢復時間（模糊檢查點 fuzzy checkpoint：begin_checkpoint / end_checkpoint 包夾，髒頁非同步刷回）。
崩潰恢復：redo 與 undo#
斷電重啟後，磁碟上可能有：已提交但髒頁還沒刷回的變更、以及未提交事務已刷回的半成品（取決於 steal/force 策略）。恢復要把資料庫拉回最後一致狀態。
steal/force 策略決定恢復需要什麼日誌：
| 策略 | 含義 | 對恢復的影響 |
|---|---|---|
| Steal | 允許提交前刷回該事務的髒頁 | 需要 undo（回滾未提交的刷回） |
| No-steal | 不准刷回未提交事務的頁 | 不需 undo，但要大頁快取 |
| Force | 提交前必須刷回所有修改頁 | 不需 redo，但提交慢（多 I/O） |
| No-force | 允許部分修改頁未刷回就提交 | 需要 redo（重放已提交未刷回） |
主流引擎走 steal + no-force，所以 redo 與 undo 都要 ── 這就是 ARIES 演算法，分三階段：
- 分析（Analysis）：掃描日誌，找出崩潰時的髒頁集合（決定 redo 起點）與進行中事務集合（決定 undo 對象）
- 重做（Redo）：從起點開始重放歷史，把已提交但未刷回、以及未完成事務的變更全部重放，恢復到崩潰當下的頁面狀態（物理 redo，加速恢復）
- 撤銷（Undo）：按逆時間順序回滾所有未完成事務，回到最後一致狀態（邏輯 undo，提高正常運行並發度）
Undo 操作本身也要寫日誌（補償日誌記錄 CLR, Compensation Log Records），這樣即使恢復過程中又崩潰，重啟也能正確接續，不會重複撤銷。
實務常見組合：物理日誌做 redo（重放快、不依賴當前狀態）、邏輯日誌做 undo（如「為鍵 Y 插入記錄 X 的逆操作」，並發友善）。
B-Tree 分裂 vs LSM 寫入：對比#
把本章的就地分裂與 15 RocksDB 與 LSM-Tree 的 append 路徑並排，差異一目了然：
| 維度 | B-Tree 分裂 | LSM-Tree 寫入 |
|---|---|---|
| 寫入路徑 | 遍歷到葉 ➡️ 就地改 ➡️ 可能連鎖分裂 | append 到 WAL + memtable，不定位舊記錄 |
| 結構變更 | 同步發生在寫入路徑上（分裂/合併） | 推遲到後台 compaction |
| 磁碟 I/O | 隨機（定位頁）+ 順序（WAL） | 幾乎全順序 |
| 原子性手段 | WAL + ARIES redo/undo | WAL（memtable 重建）+ 不可變檔案 |
| 並發保護 | latch（物理）+ lock（邏輯） | reference counting（檔案不可變免閂鎖） |
| 空間放大 | 預留空間，佔用率低至 50% | 多版本暫存，compaction 前較高 |
| 寫放大來源 | 回寫 + 同頁重複更新 + 分裂搬移 | compaction 把資料在層間重寫 |
兩者寫放大的來源不同，不能直接比數字。B-Tree 的放大來自就地回寫與分裂搬移；LSM 來自 compaction 跨檔案遷移。
Latch：並行下的物理保護#
03 章的「鎖」保護的是邏輯資料（鍵、鍵範圍），持續整個事務。但多執行緒同時動同一個 B-Tree 頁時，保護的是物理結構（頁內容、樹形狀），這用更輕量的 latch（閂鎖）：
| 維度 | Lock（鎖） | Latch（閂鎖） |
|---|---|---|
| 保護對象 | 邏輯內容（鍵 / 範圍） | 物理表示（頁內容、樹結構） |
| 粒度 | 鍵 / 範圍 | 頁 |
| 持有時長 | 整個事務 | 極短（操作期間） |
| 管理者 | 資料庫鎖管理器 | 樹實作內部 |
| 死鎖 | 偵測 + 回滾 | 靠程式設計避免（不做偵測） |
物理操作的干擾分三類：並行讀（多讀者讀同頁）、並行更新（多寫者改同頁）、讀寫重疊。用讀寫鎖（RW latch）：多讀者可並行，寫者要排他。
Latch crabbing（閂鎖蟹行）#
為了縮短持有時間：從根往下走，拿到子節點 latch 後就釋放父節點 latch ── 像螃蟹一隻腳落地另一隻才抬起。
- 讀路徑：拿到子 latch ➡️ 立刻放父 latch
- 插入路徑：若子節點未滿（不會向上傳播分裂）➡️ 放父 latch
- 刪除路徑：若子節點元素夠多（不會合併）➡️ 放父 latch
這是樂觀的：大多數插入/刪除不會連鎖傳播，且越往上層傳播機率越低。寫入可先在葉層拿排他 latch，需要分裂再沿樹向上升級。因為根節點是必經之路、又最後才分裂，所以根可以總是樂觀閂鎖。PostgreSQL 的 Blink-Tree 進一步用 high key + 兄弟指標，允許「下降到子層時不持父鎖」，把結構修改時持有的鎖數降到常數，並發更高。
小結#
- 頁分裂：定位葉 ➡️ 滿則分裂搬一半 ➡️ 提升分隔鍵到父；葉複製鍵、內部移動鍵
- 連鎖分裂可一路到根，只有根分裂才讓樹長高
- 合併/借位處理低佔用頁；50% 是分裂後的佔用率下界，B-Tree 用空間換寫入彈性
- WAL 鐵律：先把日誌落盤，才改頁；提交以 COMMIT 記錄落盤為準
- 崩潰恢復走 ARIES：分析 ➡️ redo（物理、重放歷史）➡️ undo（邏輯、逆序回滾），undo 也記日誌
- latch 保護物理結構（短、頁級、不偵測死鎖），lock 保護邏輯資料（長、事務級）；crabbing 與 Blink-Tree 提升並發
下一節把鏡頭轉向儲存引擎的記憶體與磁碟結構全貌 ── SSTable 內部格式、memtable、fsync 策略與快取置換。