什麼是索引？

索引是資料庫管理系統中一個排序的資料結構，以輔助快速查詢、更新資料表資料。實現通常採用 B 樹 及其變種 B+ 樹。

除了資料本身，資料庫系統維護滿足特定尋找演算法的資料結構，這些結構以指標引用資料，使高級尋找演算法得以在其上執行——這就是索引。

索引的代價與收益

代價	收益
增加儲存空間	唯一性索引保證資料唯一
INSERT/UPDATE/DELETE 需同步維護索引，耗時	大幅加速資料檢索（核心理由）
聚簇索引空間更大	加速表連結、參考完整性檢查
	分群/排序子句效能顯著提升
	優化器可利用索引產生更優執行計畫

何時建立、何時不建立索引

✅ 建議建立索引的欄位

• 頻繁出現在 WHERE、JOIN ON、ORDER BY、GROUP BY 的欄位
• 主鍵、外鍵欄位
• 範圍查詢欄位（索引已排序，範圍連續）
• 高選擇性（基數大）欄位

❌ 不建議建立索引的欄位

• 極少查詢或參考的欄位
• 基數極低欄位（如性別、狀態碼）
• TEXT、BLOB、BIT 等大物件/低基數類型
• 寫入頻率遠高於讀取的表/欄位

索引分類

• 唯一索引：不允許重複鍵值
• 主鍵索引：唯一索引特例，自動建立，不允許 NULL
• 聚集索引：資料物理順序 = 索引邏輯順序，每表僅一個（InnoDB 主鍵即聚集索引）
• 非聚集索引：葉節點存主鍵值，需回表查資料

局部性原理與磁碟預讀——B 樹為何高效

• 磁碟存取速度約為記憶體的 百分之一，機械尋道是瓶頸。
• 作業系統以 頁（Page，通常 4 KB） 為單位交換資料；讀取一筆資料時，順帶讀入相鄰頁（預讀）。
• 局部性原理：被存取資料的鄰近資料短時間內大概率會被用到。

B 樹節點 = 1 頁

• 每個節點大小設為 1 頁 → 讀取節點只需 1 次 I/O。
• 新建節點直接申請 1 頁空間，利用頁對齊特性，保證節點物理連續。
• 樹高 h 極小（出度 d 通常 > 100），h ≤ 3 覆蓋千萬級資料。
• 根節點常駐記憶體 → 查詢最多 h-1 次磁碟 I/O，漸近複雜度 O(log_d N)。

紅黑樹為何不適合

• 邏輯鄰近（父子）物理可能離散，無法利用預讀與局部性。
• 樹高 h 明顯更深，I/O 次數大增。

B 樹 vs B+ 樹

特性	B 樹	B+ 樹
節點內容	鍵值 + 資料指標	非葉節點僅存鍵值（索引），葉節點存全量鍵值 + 資料指標
資料分布	資料分散在各層節點	所有資料集中在葉節點，葉節點雙向鏈表串聯
查詢路徑	命中即回傳，可能不達葉節點	無論成否，必走至葉節點（層數固定）
範圍查詢	需中序遍歷，較慢	葉節點鏈表掃描，極快
插入/刪除	複雜，可能在非葉節點	僅在葉節點操作，較簡單

InnoDB 採用 B+ 樹的關鍵優勢

1. 穩定查詢效能：所有查詢走相同層數，無「命中內部節點快、命中葉節點慢」的抖動。
2. 範圍掃描極快：葉節點鏈表支援 BETWEEN、>、< 等範圍查詢零成本定位起點、順序讀取。
3. 非葉節點更瘦：不存資料指標，單頁容納更多鍵值 → 出度更大 → 樹高更低。
4. 全表掃描友好：只需遍歷葉節點鏈表，無需遞迴內部節點。

效能分析總結

• 以 磁碟 I/O 次數 衡量索引優劣。
• B+ 樹配合「節點=頁」+「預讀」+「局部性」，實現 O(log_d N) 極低 I/O 查詢。
• 實務上 d > 100，h ≤ 3，百萬級表單次查詢 ≤ 3 次 I/O。

建議深入學習

• B 樹 / B+ 樹插入、分裂、合併、旋轉完整演算法
• InnoDB 聚集索引與二級索引互動（回表、覆蓋索引、索引下推 ICP）
• EXPLAIN 輸出中 type=ref/range/index/ALL 對應的 B+ 樹遍歷行為

---

圖片來源：原文保留之示意圖（https://img13.3lian.com/...），如失效請自行補充 B+ 樹結構圖。