MySQL 索引原理與資料結構深度解析：B-Tree 與 Hash 索引

MySQL 索引原理與資料結構深度解析

在 MySQL 資料庫中，索引是提升查詢效能的關鍵機制。根據功能與實作方式的不同，MySQL 索引主要分為三大類：

1. 主鍵索引

主鍵索引是針對主鍵欄位建立的唯一索引，不允許有 NULL 值，且一張表只能有一個主鍵索引。它是資料行唯一性的強力保證，InnoDB 存儲引擎會將表數據按照主鍵順序組織存放（聚簇索引）。

2. 常規索引

常規索引（普通索引）是最基本的索引類型，沒有唯一性限制，允許 NULL 值。其底層實作主要採用 B+ 樹 和 哈希表 兩種資料結構，適用於大多數查詢場景。

3. 全文索引

全文索引專門用於文本搜尋，實作原理類似倒排索引，能高效支援「包含關鍵字」的模糊查詢需求，常用於文章搜尋、日誌分析等場景。

核心資料結構回顧：B-Tree 與 Hash Table

B-Tree（B+ 樹）特性詳解

B 樹是一種多路平衡查找樹，能在 O(log n) 時間複雜度內完成插入、刪除、查找等動態集合操作。除資料庫索引外，也廣泛應用於檔案系統的磁碟查找。其核心屬性如下：

• 根節點特性： 若根節點非葉節點，至少擁有兩棵子樹。
• 關鍵字數量限制： 非根節點包含的關鍵字個數 j 滿足：⌈m/2⌉ - 1 ≤ j ≤ m - 1（m 為樹的階數）。
• 度數關係： 非葉節點的度數 = 關鍵字總數 + 1，內部子樹個數 k 滿足：⌈m/2⌉ ≤ k ≤ m。
• 葉節點同層： 所有葉節點位於同一層級，確保查詢路徑長度一致。
• 有序性： 每個節點內的元素按從小到大排序，支援範圍查詢與排序操作。

在 MySQL InnoDB 中，實際採用的是 B+ 樹（B-Tree 的變體）：非葉節點僅存儲索引鍵值，不存儲實際數據；葉節點通過雙向鏈表連結，並存儲完整數據行，極大優化了範圍掃描與全表掃描效能。

Hash 索引特點

Hash 索引基於哈希表實作，僅支援精確匹配查詢（=、IN、<=>），查詢時間複雜度接近 O(1)，速度極快。但不支援範圍查詢、排序、最左前綴匹配，且易發生哈希碰撞導致效能退化。Memory 存儲引擎預設使用 Hash 索引，InnoDB 會自適應建立自適應哈希索引（AHI）加速熱點數據訪問。

選型建議

• 需支援範圍查詢、排序、分組：選 B+ 樹索引
• 僅做精確查找、數據分布均勻：可考慮 Hash 索引
• 文本搜尋場景：使用全文索引