MySQL 中的索引是資料庫效能最佳化的關鍵因素之一。在設計和實作索引的資料結構時，MySQL 選擇了 B+ 樹 作為主要的儲存結構。這種選擇在查詢效能、磁碟I/O 效率等方面表現出色。然而，B+ 樹並不是唯一的索引實作方案，常見的替代資料結構還有 哈希表、二元樹、B 樹 和 跳表。本文將詳細分析這些資料結構的特點，比較它們的優缺點，並專注於MySQL 為什麼最終選擇了B+ 樹。
1. 資料庫索引和資料結構的關係
在資料庫中，索引是一種用於快速查找資料的資料結構，能夠顯著提升資料查詢效能。在大規模資料的查詢場景中，選擇合適的資料結構直接決定了索引的效率。理想的索引結構應具備下列幾項特性：
- 尋找高效：能快速找到特定數據。
- 儲存緊湊：在盡可能少的磁碟空間下儲存更多資料。
- 維護成本低：資料結構插入、刪除時能夠保持高效率。
- 支援範圍查詢：資料庫查詢不僅包括精確查詢，還經常涉及範圍查詢，例如
BETWEEN操作。
為了實現這些目標，資料庫系統評估了多種資料結構，最終選擇了B+ 樹。接下來，我們將逐一介紹這些資料結構的特性、優缺點及其適用場景。
2. 常見資料結構的特性與應用
1. 哈希表（Hash Table）
特點
- 實現：透過哈希函數將資料映射到不同的儲存位置，鍵和值一一對應。
- 查詢時間複雜度：理想情況下，查詢時間複雜度為O(1)，效率極高。
- 不支援範圍查詢：哈希表只能用於精確查詢，無法有效支援範圍查詢。
優缺點
- 優點：查詢和插入速度快，尤其適用於等值查詢。
- 缺點：哈希表不支援順序訪問，因此無法進行範圍查詢。
- 適用場景：等值查詢，如使用者ID 查詢；對於頻繁的插入和刪除操作，哈希表的效能較好。
總結
在資料庫索引設計中，哈希表適合需要高效精確查找的場景，但由於缺乏順序性和範圍查詢支持，MySQL 沒有選擇哈希表作為主要索引結構。
2. 二元樹（Binary Tree）
特點
- 實現：每個節點最多有兩個子節點，分別為左子節點和右子節點。
- 查詢時間複雜度：理想情況下為O(log n)，但在不平衡情況下會退化成O(n)。
- 需要平衡操作：對於不平衡的二元樹，需要額外的平衡操作（如紅黑樹、AVL 樹）。
優缺點
- 優點：支援範圍查詢，樹狀結構支援順序存取。
- 缺點：插入和刪除操作複雜度較高，維護成本較大；在資料規模較大時，二元樹的層級較深，導致磁碟I/O 操作增加。
- 適用場景：適合小規模的、結構相對簡單的資料集。
總結
二元樹在資料量大時會退化成鍊錶，查詢效率降低，且不易在磁碟儲存中實作。對於大型資料庫索引而言，不適合作為索引的資料結構。
3. B 樹（B-Tree）
特點
- 實現：多叉平衡樹，非葉子節點可以儲存資料。每個節點包含多個鍵值，保持平衡結構。
- 查詢時間複雜度：O(log n)。
- 支援順序存儲：B 樹的節點依序儲存數據，支援範圍查詢。
優缺點
- 優點：平衡多叉結構層級較淺，查找速度較快，適合大規模資料的管理。
- 缺點：由於資料儲存在所有節點上，查詢操作會導致大量磁碟I/O。
- 適用場景：B 樹適用於需要順序尋找和範圍查找的場景，在檔案系統索引中較為常用。
總結
儘管B 樹適用於範圍查詢，但它將資料保存在每個節點上，增加了磁碟I/O 次數，降低了查詢效率。這是B 樹在資料庫索引設計中不被優先選擇的原因。
4. 跳表（Skip List）
特點
- 實現：在有序鍊錶基礎上，增加多層索引，每層索引可以跨越多個節點，加速查詢。
- 查詢時間複雜度：O(log n)。
- 支援範圍查詢：跳表中資料有序，支援高效率的範圍查詢。
優缺點
- 優點：結構簡單，支援快速查找、插入和刪除；可以有效率地進行範圍查詢。
- 缺點：跳表節點多層索引會佔用較多空間；適合記憶體中的資料管理，在磁碟中效能一般。
- 適用場景：適合基於記憶體的KV 資料庫，如Redis。
總結
跳表適用於記憶體資料庫中的索引結構，但由於其空間效率不高且磁碟效能不佳，在MySQL 中並未選擇跳表作為主要的索引結構。
5. B+ 樹（B+ Tree）
特點
- 實現：B+ 樹是B 樹的變種，所有資料僅儲存在葉子節點，非葉子節點只儲存鍵值作為索引。葉子節點透過鍊錶連接，支援順序存取。
- 查詢時間複雜度：O(log n)。
- 支援順序和範圍查詢：B+ 樹的葉子節點依序排列，方便順序掃描和範圍查詢。
優缺點
- 優點：層級淺，資料集中儲存在葉子節點，非葉節點僅用於索引，減少了磁碟I/O 操作。鍊錶結構的葉子節點支援高效的範圍查詢。
- 缺點：結構較為複雜，維護成本相對較高。
- 適用場景：適合大規模資料的磁碟儲存管理，尤其是資料庫索引。
總結
B+ 樹的結構適合磁碟存儲，查詢效率高，支援範圍查詢，兼顧了空間和效能，是MySQL 索引結構的最佳選擇。
3. MySQL 為什麼選擇B+ 樹作為索引結構？
透過對上述資料結構的分析，我們可以總結出B+ 樹在資料庫索引設計上的獨特優勢。
1. 磁碟I/O 效率高
資料庫的資料量通常非常龐大，完全載入到記憶體中並不現實，因此索引結構需要頻繁與磁碟互動。 B+ 樹的結構讓資料都儲存在葉子節點，非葉節點僅作為索引用，佔用較少的空間，能在記憶體中載入更多節點，減少了磁碟I/O 次數。此外，B+ 樹的多叉結構使得層級較淺，大幅提升了查找效率。
2. 支援範圍查詢
B+ 樹的葉子節點透過鍊錶連接，可以直接進行順序掃描。這種特性非常適合範圍查詢需求，例如 BETWEEN 操作，可以快速遍歷出滿足條件的資料集合。相較之下，哈希表和跳表無法有效支援範圍查詢，因此不適合用於資料庫索引。
3. 良好的緩存命中率
B+ 樹節點分層存儲，非葉節點只儲存鍵值，不儲存資料。這樣的設計使得MySQL 能將更多的索引節點載入記憶體中，提升快取命中率，進一步加快查找速度。而且，B+ 樹的多層結構適合在大數據量下將索引載入到不同層級的快取中，減少磁碟讀取頻率。
4. 利於順序插入和批量插入
B+ 樹支援順序插入和批次插入操作，
且由於結構穩定，插入操作不會像二元樹那樣因不平衡而頻繁進行複雜的平衡調整操作，維護成本較低。 MySQL 索引的儲存特性使得它在頻繁的資料寫入和刪除過程中能有效保持結構的穩定性。
4. 總結
MySQL 選擇B+ 樹作為索引結構，是基於對索引高效性、資料量適應性、磁碟I/O 效率和範圍查詢需求的綜合考量。 B+ 樹的多層儲存和有序鍊錶結構使得它在大資料量查詢中具有顯著的效能優勢，是支援關係型資料庫索引的理想選擇。
透過理解MySQL 索引的資料結構設計原理，可以幫助開發者在實際應用中更好地利用索引，提高查詢效能。同時，選擇合適的查詢與排序方案、合理使用索引，能進一步優化資料庫的查詢效率。