深入解析資料庫索引實現原理：從B樹到B+樹的演進

資料庫索引是資料庫管理系統中用於加速查詢與更新的核心機制，本質上是一種經過排序的資料結構。主流資料庫系統（如MySQL的InnoDB引擎）普遍採用B樹及其變體B+樹作為索引的底層實現。理解索引原理，不僅有助於SQL優化，更能讓開發者在架構設計時做出更明智的決策。

索引的本質與代價

除了資料本身，資料庫系統還維護著滿足特定查找演算法的資料結構——索引。它們透過指標引用實際資料，使得高級查找演算法得以在索引層面執行。然而，建立索引並非零成本：一是佔用額外儲存空間，二是資料異動（INSERT/UPDATE/DELETE）時需同步維護索引，增加寫入開銷。

上圖示範一種索引方式：左側為資料表（兩欄七筆），最左欄為物理地址（邏輯相鄰不代表物理相鄰）。為加速Col2查找，右側維護一棵二元搜尋樹，節點包含索引鍵值與指向資料物理地址的指標，查找複雜度降為O(log₂n)。

索引的五大優勢

1. 唯一性約束：唯一索引確保每列資料唯一。
2. 大幅提升檢索速度：這是建立索引的核心動機。
3. 加速表連接：特別是在外鍵關聯與參考完整性驗證上效果顯著。
4. 優化分組與排序：GROUP BY、ORDER BY 可利用索引有序特性減少排序開銷。
5. 查詢優化器輔助：索引提供統計資訊，助優化器生成更優執行計畫。

為何不給每個欄位都加索引？

索引的三大劣勢：

1. 維護成本隨資料量增長：建立與維護索引耗時。
2. 佔用物理空間：聚簇索引更需較大空間。
3. 寫入效能下降：資料異動需動態維護索引，降低維護速度。

索引建立策略：該加與不該加

建議建立索引的場景

• 頻繁出現在WHERE條件、JOIN條件、ORDER BY/GROUP BY子句的欄位
• 主鍵欄位（強制唯一性與組織儲存結構）
• 外鍵欄位（加速關聯查詢）
• 範圍查詢欄位（索引有序，範圍連續）

不建議建立索引的場景

• 查詢中極少使用的欄位（維護成本＞收益）
• 基數極低的欄位（如性別，結果集佔比大，全表掃描更快）
• TEXT、IMAGE、BIT等大型或低基數類型
• 寫入頻率遠高於讀取的場景（索引拖慢寫入）

三大核心索引類型

• 唯一索引：不允許重複鍵值；現有資料有重複則無法建立。
• 主鍵索引：唯一索引的特例，自動建立，支援快速訪問。
• 聚集索引：資料物理順序與索引邏輯順序一致，每表僅一個；非聚集索引則不匹配。聚集索引通常提供更快訪問。

局部性原理與磁碟預讀：B樹設計的基石

磁碟存取速度遠慢於主存（數百分之一），機械尋道是主要瓶頸。為減少I/O，作業系統採用「預讀」機制：每次讀取一頁（通常4KB）或其整數倍。理論依據是局部性原理——當某資料被訪問，其鄰近資料大概率很快被用到。順序讀取無需尋道，僅需極少旋轉延遲，效率極高。

資料庫系統巧妙利用此特性：將B樹節點大小設定為一頁，使單節點載入僅需一次I/O。實現技巧：新建節點時直接申請一頁空間，配合頁對齊分配，確保節點物理連續。

B樹與B+樹效能分析

B樹檢索最多訪問h個節點（h為樹高），根節點常駐內存，故最多h-1次I/O，複雜度O(log_dN)。實際應用中出度d極大（通常>100），樹高h極小（≤3），效能極高。紅黑樹雖同為O(h)，但邏輯鄰近節點物理可能離散，無法利用局部性，I/O效率遠遜於B樹。

B樹與B+樹核心差異

B+樹透過「冗餘換穩定」的設計，成為關係型資料庫索引的主流選擇。

建議：深入學習B樹與B+樹資料結構，是掌握資料庫核心技術的必修課。