MySQL 索引底層原理深度解析：B+Tree 結構、存儲引擎實現與高性能策略

索引本質：有序的數據結構

MySQL 官方定義：索引是幫助 MySQL 高效獲取數據的數據結構。本質上是為了繞過順序掃描 O(n)，通過 B+Tree 實現 O(log n) 查找。

為什麼選 B+Tree？

從二叉樹到 B+Tree 的演進

• 二叉搜索樹：高度 h=O(log n)，但磁盤存儲時節點分散，無法利用局部性原理，I/O 次數 = h
• B-Tree：多路平衡樹，節點大小 = 頁大小（4KB/16KB），一個節點一次 I/O 載入，高度 h=O(log_d n)，d 為度（通常 100+），h≤3
• B+Tree：內節點只存 key，葉節點存數據 + 雙向鏈表，範圍查詢掃描葉鏈表極快，出度 d 更大，高度更低

磁盤預讀與局部性原理

• 磁盤順序讀取極快（無尋道、少旋轉）
• 預讀一頁（4KB/16KB）載入內存
• B+Tree 節點大小 = 頁大小，一次 I/O 載入一節點
• 非葉節點無數據，Key 更多，出度更大，樹更矮

MySQL 存儲引擎索引實現差異

MyISAM：非聚簇索引

• 索引文件（.MYI）與數據文件（.MYD）分離
• 主索引/輔助索引結構相同：B+Tree 葉節點存 數據文件物理地址
• 主索引要求 Key 唯一，輔助索引允許重複

InnoDB：聚簇索引

• 數據文件即主索引：.ibd 按主鍵 B+Tree 組織，葉節點存 完整行數據
• 輔助索引葉節點存 主鍵值（而非地址）
• 查詢輔助索引需「回表」：輔助索引 → 主鍵值 → 主索引 → 行數據
• 必須有主鍵：無顯式主鍵 → 選唯一非空索引 → 生成 6 字節隱藏 RowID

對比總結

InnoDB 主鍵選擇鐵律：自增整數

自增主鍵：順序追加，頁分裂少，存儲緊湊

-- 理想情況：頁填滿 → 分配新頁 → 續寫
-- 無數據移動、無碎片、無額外 I/O

非自增主鍵（UUID/業務鍵）：隨機插入，頁分裂頻繁

-- 隨機位置插入 → 頁移動、分裂、碎片
-- 目標頁可能已刷盤 → 讀回 → 修改 → 刷盤
-- 導致寫放大、空間浪費、OPTIMIZE TABLE 維護

高性能索引策略實戰

1. 最左前綴原則

INDEX idx_a_b_c (a, b, c)
WHERE a=1                 -- ✅ 用到 a
WHERE a=1 AND b=2         -- ✅ 用到 a,b
WHERE a=1 AND c=3         -- ⚠️ 只用到 a
WHERE b=2                 -- ❌ 無法使用

2. 範圍查詢阻斷後綴列

WHERE a=1 AND b>2 AND c=3  -- 只用到 a,b（b 是範圍）

3. 覆蓋索引：避免回表

INDEX idx_a_b (a, b)
SELECT a, b FROM t WHERE a=1; -- Extra: Using index，只掃描索引

4. 前綴索引：長字符串權衡

-- 原 VARCHAR(100) 索引大
-- 分析選擇性
SELECT COUNT(DISTINCT LEFT(email, 10))/COUNT(*) FROM users; -- 0.92
-- 創建前綴索引
ALTER TABLE users ADD INDEX idx_email_prefix (email(10));

缺點：不可用於 ORDER BY/GROUP BY/覆蓋索引

5. 索引下推 (ICP, 5.6+)

WHERE 條件下推到存儲引擎過濾，減少回表。EXPLAIN 顯示 Using index condition。

6. 排序優化：索引順序匹配 ORDER BY

INDEX idx_a_b (a, b)
ORDER BY a, b       -- ✅ 索引順序直接返回
ORDER BY a DESC, b  -- ⚠️ 8.0+ 支持降序索引
ORDER BY b, a       -- ❌ 需 filesort

employees 模擬數據庫實戰分析

-- titles 表主鍵 (emp_no, title, from_date)
EXPLAIN SELECT * FROM titles 
WHERE emp_no=10001 AND title='Senior Engineer' AND from_date='1986-06-26';
-- type=const, key=PRIMARY, key_len=59 (全鍵匹配)

EXPLAIN SELECT * FROM titles WHERE emp_no=10001;
-- type=ref, key=PRIMARY, key_len=4 (只用 emp_no)

EXPLAIN SELECT * FROM titles WHERE emp_no=10001 AND from_date='1986-06-26';
-- type=ref, key=PRIMARY, key_len=4 (title 缺失，from_date 無法用到)

-- 填坑優化：title 值少用 IN 列舉
EXPLAIN SELECT * FROM titles 
WHERE emp_no=10001 
  AND title IN ('Senior Engineer','Staff',...) 
  AND from_date='1986-06-26';
-- type=range, key_len=59 (全鍵用上)

索引選擇性與基數

Selectivity = COUNT(DISTINCT col) / COUNT(*)
-- 選擇性接近 1：優秀（如主鍵、唯一鍵）
-- 選擇性 < 0.01：極差（如性別、狀態），建索引收益低

總結：索引優化心法

1. 理解 B+Tree：頁、節點、分裂、合並、葉鏈表
2. 區分聚簇/非聚簇：InnoDB 主鍵即數據，輔助索引存主鍵
3. 主鍵用自增整數：順序寫入、無碎片、輔助索引瘦身
4. 最左前綴 + 覆蓋索引：聯合索引設計核心
5. 讀懂 EXPLAIN：type、key、key_len、rows、Extra
6. 業務駅動索引：慢查詢日誌 + EXPLAIN + 測試驗證，而非理論臆造

參考文獻

1. 《高性能 MySQL》第 3 版 - Baron Schwartz 等
2. 《MySQL 技術內幕：InnoDB 存儲引擎》 - 姜承堯
3. MySQL 8.0 官方文檔 - Indexes 章節
4. D. Comer, "Ubiquitous B-tree", ACM Computing Surveys, 1979