從樹形結構到 B+樹
演進脈絡
- 二叉搜尋樹：高度隨資料線性增長，磁碟 IO 次數不可控。
- B-Tree：多路平衡樹，非葉節點也存資料，範圍查詢需中序遍歷。
- B+Tree：資料僅存葉節點、葉節點雙向鏈表、非葉節點僅存索引鍵值 → 範圍掃描極快、單次查詢 IO 穩定。
- B*Tree：非葉節點也加鏈表、分裂策略更積極（2/3 填充因子），資料庫較少採用。
為什麼資料庫選 B+樹？
磁碟 IO 為瓶頸。B+樹扁平（高度 3~4）、節點大小對齊頁（16KB）、非葉節點常駐內存、葉節點鏈表支援範圍掃描 → 單點查詢 1~3 次磁碟 IO，範圍查詢順序讀取。
InnoDB 存儲架構：聚簇索引 vs 二級索引
聚簇索引
- 主鍵 B+樹葉節點直接包含完整行資料。
- 主鍵查詢：單棵樹遍歷至葉節點即得全行。
二級索引
- 索引鍵 + 主鍵值（而非物理位址）。
- 查詢流程：二級索引樹找主鍵 → 回主鍵索引樹查全行（「回表」）。
設計優勢
- 主鍵查詢零回表，極快。
- 行移動/頁分裂時，二級索引無需更新（主鍵值不變），維護成本低。
頁結構：InnoDB 管理的最小單位（16KB）
頁類型
- Index Page (B-tree Node) — 存放索引記錄
- Undo Log Page
- System Page (FSP_HDR, IBUF_BITMAP, INODE)
- Transaction System Page
頁頭關鍵欄位
PAGE_N_DIR_SLOTS：目錄槽數（Page Directory，加速頁內二分查找）。PAGE_N_RECS：記錄數。FIL_PAGE_PREV/NEXT：雙向鏈表指標。PAGE_LEVEL：樹層級（0=葉節點）。PAGE_INDEX_ID：所屬索引 ID。
記錄格式四類
| 類型 | 顏色 | 關鍵欄位 |
|---|
| 主鍵非葉節點 | 綠 | Min Cluster Key、Child Page No |
| 主鍵葉節點 | 黃 | Cluster Key + Non-Key Fields（完整行） |
| 二級非葉節點 | 藍 | Min Secondary Key + Cluster Key + Child Page No |
| 二級葉節點 | 紅 | Secondary Key + Cluster Key |
註：二級非葉節點含主鍵以保證唯一性（二級鍵可重複）。
全景圖：B+樹與頁的對應
- 一個頁可存多個 B+樹節點（記錄）。
- 頁分裂 ≠ 節點分裂：頁滿時分裂頁，節點邏輯分裂由上層協調。
- Page Directory（頁目錄）提供頁內二分查找，跳過單向鏈表掃描。
實測：一張 22.1GB 表的 B+樹高度僅 3
- 葉節點/頁 ≈ 468 行，非葉節點/頁 ≈ 1200 鍵值（1200 路）。
- 高度 3 支撐 22.1GB；高度 4 理論支撐 25.9TB。
- 非葉節點總大小 < 18.8MB，全載入內存後單點查詢僅 1 次磁碟 IO。
實戰優化原則
- 主鍵單調遞增（自增/雪花 ID），避免頁分裂與碎片。
- 主鍵越短越好：二級索引葉節點儲存主鍵，主鍵膨脹會放大所有二級索引體積。
- 覆蓋索引：查詢欄位全在二級索引中 → 避免回表。
- 最左前綴：複合索引
(a,b,c) 支援 a、a,b、a,b,c 查詢。
- 定期 OPTIMIZE TABLE / ALTER TABLE ... ENGINE=InnoDB 整理碎片。
參考資源
- 《高效能 MySQL》第 3 版，第 3 章 索引。
- MySQL 官方文檔：InnoDB Index Structures。
- Percona Blog：InnoDB Page Structure Deep Dive。
copyright ©
萬盛學電腦網 all rights reserved