B 樹與 B+ 樹原理及在 MySQL 索引中的應用深度解析
1. B 樹（B-Tree）定義與特性
B 樹是一種平衡的多路查找樹，常用於檔案系統。一棵 m 階 B 樹滿足：
- 每個節點最多有 m 個子節點。
- 根節點若非葉子，至少有兩個子節點。
- 非根非葉節點至少有
⌈m/2⌉ 個子節點。
- 節點包含
(n, A0, K1, A1, ..., Kn, An)：Ki 為關鍵字（遞增），Ai 為子節點指針，n 為關鍵字個數。
- 所有葉子節點同層，深度相等（樹高）。
2. B 樹查找、插入、刪除算法
查找過程：從根節點開始，在節點內部有序表中查找，若命中則成功；否則按指針下沉，直到葉子節點。
插入：在最底層非終端節點添加關鍵字，若超過 m-1 則分裂，中間鍵上移至父節點，可能引發連鎖分裂至根。
刪除：從節點移除關鍵字，若節點鍵數少於 ⌈m/2⌉-1，則向兄弟借鍵或與兄弟合併，可能向上傳遞。
3. B+ 樹：B 樹的變體，專為磁盤存儲優化
差異點：
- 非葉節點僅存關鍵字與子節點指針，不存資料記錄。
- 葉節點包含所有關鍵字及對應資料指針，並以雙向鏈表連接，支援範圍掃描與全表掃描。
- 非葉節點可視為稀疏索引，葉節點為稠密索引。
4. 為什麼資料庫索引選擇 B+ 樹？
磁盤預讀與局部性原理
- 磁盤 I/O 成本遠高於記憶體，需盡量減少 I/O 次數。
- 作業系統以「頁」（通常 4KB/16KB）為單位預讀，順序讀取極快。
- 將 B+ 樹節點大小設為一頁，每次讀取一個節點僅需 1 次 I/O。
樹高優勢
B+ 樹階數 m 很大（通常 >100），樹高 h ≈ log_m(N) 很小（通常 ≤3）。查找最多 h-1 次 I/O（根節點常駐記憶體），漸進複雜度 O(log_m N)。紅黑樹等二叉樹高度大，邏輯相鄰節點物理離散，無法利用預讀，I/O 複雜度同為 O(h) 但常數因子大得多。
5. MySQL 中的 B+ 樹索引實現
MyISAM：非聚集索引
- 主鍵索引：葉節點
data 域存資料行地址。
- 輔助索引：結構相同，葉節點同樣存地址。主鍵與輔助索引無本質區別，僅主鍵要求唯一。
- 檢索流程：索引樹搜尋 → 取地址 → 回表讀取資料。
InnoDB：聚集索引
- 表資料文件本身即主鍵索引（B+ 樹），葉節點存完整行資料。
- 輔助索引葉節點存主鍵值而非地址。查詢需「回表」：先搜輔助索引得主鍵，再搜主鍵索引得行資料。
- 因此主鍵宜短（如自增整數），避免輔助索引膨脹；主鍵宜單調遞增，減少頁分裂。
6. 總結
B+ 樹憑藉「節點即頁、樹高極低、葉節點鏈表支援範圍查詢」三大特性，成為關係型資料庫索引的首選結構。理解 MyISAM 與 InnoDB 索引實現差異，對優化查詢、設計主鍵、選擇索引策略至關重要。
