什麼是哈希索引

MySQL中的自適應哈希索引_數據庫技術_二級索引

哈希索引是基於內存的支持，底層結構就是鏈式哈希表，增刪改查的時間複雜度都是O(1)。

通過將索引鍵（如數據庫表的主鍵、Redis 的 Key）經過哈希函數計算得到哈希值，再將哈希值映射到對應的存儲位置（槽位），從而快速定位數據的物理地址或內存地址。

InnoDB自適應哈希索引

AHI 完全存儲在 InnoDB 的 緩衝池（Buffer Pool） 中，屬於緩衝池內部的一塊專用內存區域，並非獨立於緩衝池的單獨內存空間。

結構

哈希表數組（Hash Bucket Array）

  • 核心存儲結構：數組的每個元素（哈希桶）是一個指向 “哈希鏈表” 的指針。
  • 哈希函數：InnoDB 會對索引鍵（如 B+ 樹索引的鍵值）計算哈希值，根據哈希值將鍵值映射到對應的哈希桶。
  • 內存佔用：哈希表數組的大小由 InnoDB 動態調整，默認初始大小較小，隨熱點數據增多而擴容（避免哈希衝突過於頻繁）。

哈希鏈表（Hash Chain）

  • 解決哈希衝突：當多個索引鍵的哈希值映射到同一個哈希桶時，會通過鏈表形式存儲（鏈地址法）。
  • 鏈表節點內容：每個節點存儲 3 類核心信息：
  • 索引鍵的完整值（或前綴，取決於 AHI 的構建策略）；
  • 對應的 B+ 樹索引類型（聚簇索引 / 二級索引）；
  • 數據頁在緩衝池中的內存地址（或頁號），以及頁內數據的偏移量（直接定位到具體行數據）。

不使用自適應哈希索引的查詢過程

MySQL中的自適應哈希索引_數據庫技術_#哈希算法_02

  1. 解析與優化器決策：優化器選擇name二級索引（等值查詢適合二級索引），避免全表掃描。
  2. 二級索引 B + 樹遍歷（從根到葉）：
  • 與聚簇索引遍歷邏輯一致：從二級索引根節點開始，逐層查找name='苗'對應的子節點，直到葉子節點。
  • 二級索引葉子節點存儲「索引鍵（username）+ 主鍵 id」（如('苗', 100)），通過二分查找定位到username='苗'對應的主鍵 id=100。
  • 關鍵：二級索引遍歷同樣無 AHI 加速，需完整走 B + 樹逐層查找（啓用 AHI 時，熱點username會通過哈希表直接獲取主鍵 id）。
  1. 回表查詢（聚簇索引查找）：
  • 拿到主鍵 id=100 後，需通過聚簇索引查詢完整行數據（即回表），回表流程與聚簇索引等值查詢完全一致（從根到葉遍歷 B + 樹，定位葉子節點的完整行）。
  1. 數據整合與返回：將回表獲取的完整行數據返回給應用。

使用自適應哈希索引的查詢過程

在AHI中，key就是經常被訪問的索引，value就是索引對應的物理數據頁的位置。

MySQL中的自適應哈希索引_數據庫技術_二級索引_03

InnoDB 會持續監控所有索引的查詢操作，尤其是等值查詢。它會為每個索引鍵維護一個訪問計數器，記錄其被查詢的次數。當某個索引鍵的訪問次數達到內部閾值時，InnoDB 會將其視為熱點數據，並觸發 AHI 的構建。

當後續有相同的等值查詢時，InnoDB 會先檢查 AHI 的哈希表：

  • 如果找到匹配的索引鍵（哈希命中），直接通過存儲的物理地址訪問數據頁，跳過 B+ 樹的遍歷。
  • 如果未找到（哈希未命中），則 fallback 到傳統的 B+ 樹查詢，並更新該索引鍵的訪問計數器。

基於主鍵的查找，大部分都是哈希查找。

AHI 的哈希表大小是有限的（默認佔用緩衝池的 1/6），當哈希表滿時，InnoDB 會根據LRU（最近最少使用）算法淘汰掉訪問頻率較低的索引鍵，為新的熱點數據騰出空間。當索引鍵對應的記錄被刪除或更新時，InnoDB 會同步更新 AHI 中的對應條目，確保數據一致性。

條件

只有滿足以下條件，二級索引的索引鍵才會被 InnoDB 自動加入到自適應哈希索引中：

1. 查詢類型必須是等值查詢

  • AHI 僅支持等值查詢（=），不支持範圍查詢（>、<、BETWEEN）、模糊查詢（LIKE）或排序（ORDER BY）等。

2. 索引鍵值的訪問頻率足夠高

  • InnoDB 會監控索引鍵的訪問次數，只有當某個索引鍵被查詢的次數達到一定閾值時，才會將其加入 AHI。
  • 這個閾值由 InnoDB 內部算法動態決定，無法手動配置。

3. 索引鍵值的選擇性足夠好

  • 選擇性是指索引鍵值的唯一程度（選擇性 = 唯一索引值數量 / 總記錄數）。
  • AHI 更傾向於緩存選擇性高的索引鍵（如主鍵、唯一索引），因為這些索引鍵的等值查詢命中率更高，能顯著提升性能。
  • 對於選擇性極低的索引（如 gender 字段，只有男 / 女兩個值），即使訪問頻率高，InnoDB 也可能不會將其加入 AHI，因為哈希衝突的概率太高，優化效果有限。

4. 索引必須是 B+ 樹索引

  • AHI 僅作用於 InnoDB 的B+ 樹索引（包括聚簇索引和二級索引），不支持哈希索引、全文索引或空間索引。

總結

自適應哈希索引可以看作為索引的索引，只有熱索引才有資格建立起哈希索引以方便數據頁的查找。但維護哈希索引也需要一定的開銷，要根據具體的情況來決定是否開啓自適應哈希索引。