在數據庫系統中，索引是提升查詢效率的關鍵數據結構。MySQL的InnoDB和MyISAM等主流存儲引擎廣泛使用B樹（及其變體B+樹）作為索引的底層實現，這并非偶然，而是基于B樹在數據處理與存儲服務中的一系列核心優勢。

1. 適應磁盤I/O特性：減少尋道時間

數據庫數據通常存儲在磁盤上，而磁盤訪問（尤其是機械硬盤）的特點是順序讀取速度快，隨機尋道（移動磁頭）耗時高。B樹是一種多路平衡搜索樹，其每個節點可以包含多個鍵值和子節點指針（通常稱為“階”）。這種設計使得樹的高度相對較低（例如，一個3層的B樹就能存儲數百萬條記錄），從而將大多數查詢所需的磁盤I/O次數控制在很小的范圍內（通常2-3次）。相比之下，二叉樹（如AVL樹、紅黑樹）雖然平衡，但每個節點只有兩個分支，樹的高度會隨著數據量增長而快速增加，導致更多的磁盤訪問，性能急劇下降。

2. 高效的范圍查詢與順序訪問

MySQL實際使用的是B+樹，它是B樹的一種優化變體。B+樹的核心特點是：所有數據記錄（或行數據）都存儲在葉子節點中，且葉子節點之間通過指針連接成一個有序鏈表。內部節點（非葉子節點）僅存儲鍵值（索引列的值）和指向子節點的指針，不存儲實際數據。這種設計帶來了兩大好處：

• 范圍查詢高效：當執行WHERE id BETWEEN 100 AND 200這類范圍查詢時，系統只需在B+樹中找到起始鍵值所在的葉子節點，然后沿著鏈表順序遍歷即可，無需回溯到上層節點。

• 全表掃描更優：由于所有數據都在葉子節點鏈表中，順序遍歷整個表就像遍歷鏈表一樣高效，適合需要大量數據掃描的操作。

3. 穩定的查詢性能：平衡與自調整

B樹和B+樹都是“平衡”樹，意味著從根節點到任何葉子節點的路徑長度基本相同。這保證了無論數據如何分布，查詢、插入和刪除操作的時間復雜度都是O(log n)，其中n是數據量。數據庫系統需要處理頻繁的增刪改查，B樹在插入或刪除數據時能通過節點分裂與合并自動維持平衡，避免了二叉樹在極端情況下退化為鏈表（導致O(n)查詢）的風險，從而提供了可預測的性能表現。

4. 充分利用存儲塊，減少I/O浪費

磁盤和操作系統通常以“頁”（如4KB、16KB）為單位進行數據讀寫。B+樹的節點大小被設計為與磁盤頁大小對齊（例如InnoDB默認頁大小為16KB）。一個節點可以存儲大量鍵值（假設索引鍵是整型，一個頁可能存上千個鍵），這使得一次磁盤I/O能加載更多有用信息到內存，極大地提升了數據局部性和緩存效率。相比之下，如果每個節點只存少量數據，會導致頻繁的磁盤I/O，成為性能瓶頸。

5. 支持多種查詢類型

基于B+樹的索引天然支持最左前綴匹配，使得復合索引（多列索引）非常高效。例如，對(last<em>name, first</em>name)創建索引，查詢WHERE last<em>name='Smith'或WHERE last</em>name='Smith' AND first_name='John'都能有效利用索引。B+樹索引也適用于排序（ORDER BY）和分組（GROUP BY）操作，因為數據在葉子節點上已是有序狀態。

對比其他數據結構

• 哈希索引：雖然哈希表提供O(1)的單點查詢速度，但不支持范圍查詢和排序，且哈希沖突處理在磁盤上成本較高。MySQL的Memory引擎支持哈希索引，但InnoDB僅在自適應哈希索引中內部使用，主要索引仍是B+樹。
• LSM樹：在NoSQL數據庫（如LevelDB、RocksDB）中流行，它優化了寫入吞吐，但犧牲了讀取一致性。MySQL的InnoDB引擎針對OLTP（在線事務處理）場景，需要強一致的讀寫性能，B+樹仍是更合適的選擇。

###

MySQL選擇B樹（尤其是B+樹）作為索引結構的核心原因，在于它完美地平衡了磁盤I/O效率、查詢性能穩定性以及對范圍查詢和事務處理的支持。其多路平衡、節點與磁盤頁對齊、數據集中于葉子節點等特性，使得它成為關系型數據庫在面向磁盤的存儲系統中索引的理想解決方案。盡管新硬件（如SSD）和新型數據庫（如使用LSM樹的系統）帶來了不同優化思路，但B+樹在傳統OLTP領域的地位依然穩固，是MySQL高效數據處理與存儲服務的基石。