Hash 索引 vs B-Tree 索引：原理、優缺點、適用場景與 MySQL 實現差異

Hash 索引 vs B-Tree 索引：原理、優缺點、適用場景與 MySQL 實現差異

Hash 索引查詢 O(1) 極快，但功能受限；B-Tree 索引功能全面、範圍查詢高效，是 MySQL 預設主流。本文深度對比兩者原理、五大限制、InnoDB B+Tree 具體結構與選型建議。

Hash 索引特點

• 將鍵值經 Hash 函數映射為 Hash 值，存入 Hash 表（桶 + 鏈表/開放定址）。
• 等值查詢（=、IN、<=>）單次定位，無需樹遍歷。

Hash 索引五大硬傷（不適用場景）

B-Tree / B+Tree 索引（MySQL 主流）

• 所有存儲引擎（除 Archive）支援。
• 資料儲存於葉子節點，根到葉路徑長度固定，穩定 O(log N)。
• InnoDB 採用 B+Tree：葉子節點雙向鏈表，支援範圍掃描極快。
• 兩類索引：
  • 聚簇索引（主鍵）：葉子節點直接存完整行數據。
  • 二級索引：葉子節點存主鍵值，查詢需「回表」查聚簇索引。

選型建議

1. 預設用 B+Tree（InnoDB 主鍵/二級索引），覆蓋 99% 場景。
2. Memory/HEAP 引擎可選 Hash 索引，適合純等值查詢、極高並發、資料全在記憶體。
3. Oracle/PostgreSQL 支援 CREATE INDEX ... USING HASH，MySQL 僅 Memory 引擎顯式支援，InnoDB 自適應 Hash 索引（AHI）由引擎自動管理不可手動建立。

面試高頻題

Q: 1000 萬條記錄建索引，最適合哪種結構？ A: B-Tree（B+Tree）。Hash 不支援範圍查詢、排序、部分前綴，通用性差。

Q: 主鍵索引是 Hash 嗎？ A: 不是，InnoDB 主鍵是聚簇 B+Tree 索引。