B 樹 vs B+ 樹：MySQL 索引底層數據結構核心差異圖解

B 樹 vs B+ 樹：MySQL 索引底層數據結構核心差異圖解

MySQL InnoDB 存儲引擎採用 B+ 樹作為索引數據結構。理解 B 樹與 B+ 樹的差異，是掌握索引原理、優化查詢效能的基石。本文通過結構對比、優缺點分析、InnoDB 實際應用三個維度深度解析。

一、結構核心差異

二、B+ 樹在 InnoDB 中的優勢

1. 單節點容納更多索引項 → 樹高更低
   內部節點不存 RowID，同一頁面 (16KB) 可容納更多鍵值，扇出度 (Fan-out) 更大，樹高通常 2-3 層即可支撐千萬級數據，減少磁盤 IO。
2. 全表掃描/範圍查詢極快
   葉子節點雙向鏈表支持順序讀取，SELECT * FROM t WHERE id > 100 只需定位到 100 所在葉子頁，然後沿鏈表向右遍歷，無需回溯內部節點。B 樹需中序遍歷，頻繁上下跳轉。
3. 覆蓋索引天然支持
   葉子節點包含完整行數據 (聚簇索引) 或主鍵值 (二級索引)，查詢僅需索引列時直接在葉子頁完成，避免回表。
4. 穩定的查詢效能
   所有查詼必經根到葉相同深度，效能波動極小。B 樹可能在內部節點命中 (快) 或未命中需走到葉子 (慢)，方差大。

三、B 樹的優勢場景 (及 InnoDB 為何放棄)

• 熱點數據命中快：若高頻訪問的鍵值集中在上層節點，B 樹可提前返回。但資料庫訪問模式不可預測，熱點難以靜態佈局。
• 實現相對簡單：早期資料庫 (如早期 MyISAM) 採用 B 樹變體。InnoDB 為了事務、MVCC、範圍查詢、覆蓋索引綜合考量，選擇 B+ 樹。

四、InnoDB 索引實際佈局

-- 聚簇索引 (主鍵索引) 葉子頁
+------------------+------------------+------------------+
| Page Header      | Records (完整行) | Page Directory   |
| (鏈表指針、LSN)  | (按主鍵有序)     | (稀疏索引)       |
+------------------+------------------+------------------+
  ↑ prev leaf                    next leaf ↑  (雙向鏈表)

-- 二級索引 葉子頁
+------------------+------------------+------------------+
| Page Header      | Records (索引列+主鍵) | Page Directory |
+------------------+------------------+------------------+
  ↑ prev leaf                    next leaf ↑

五、實戰優化啟示

1. 主鍵選自增整數：順序寫入避免頁分裂，保持 B+ 樹葉子頁緊湊。
2. 二級索引盡量覆蓋查詢：INDEX (a,b,c) 讓 SELECT a,b FROM t WHERE a=1 僅讀索引頁。
3. 範圍查詢利用鏈表：WHERE id BETWEEN 100 AND 200 自動走葉子鏈表掃描。
4. 避免 SELECT * 觸發回表：二級索引查詢非索引列需回聚簇索引，雙倍 IO。
5. 頁面填充因子：innodb_fill_factor (MySQL 8.0+) 預留空間減少頁分裂。

六、總結

B+ 樹通過 內外節點分工 (內部導航、葉子存儲+鏈表) 和 冗餘索引鍵，換取了更低的樹高、極致的範圍查詢效能、穩定的查詢延遲，完美契合關係型資料庫「範圍查詢多、順序讀多、覆蓋索引需求大」的負載特徵，成為 InnoDB、PostgreSQL、Oracle、SQL Server 等主流引擎的首選索引結構。