阿裡面試官:設計個MySQL的Hash索引吧?

除了B-Tree 索引，MySQL還提供了如下索引：

Hash索引

隻有Memory引擎支援，場景簡單

R-Tree索引

MyISAM的一個特殊索引類型，主要用于地理空間資料類型

Full-text

MyISAM的一個特殊索引，主要用于全文索引，從MySQL 5.6開始InnoDB支援全文索引

索引 / 存儲引擎	MyISAM	InnoDB	Memory
B-Tree索引	支援
HASH索引	不支援	不支援
			不支援
Full-text索引			不支援

最常用的索引也就是B-tree索引和Hash索引，且隻有Memory，NDB兩種引擎支援Hash索引。

Hash索引适于key-value查詢，通過Hash索引比B-tree索引查詢更加迅速。但Hash索引不支援範圍查找例如<><==,>==等。

Memory隻有在"="的條件下才會使用hash索引

MySQL在 8.0才支援函數索引，在此之前是能對列的前面某一部分進行索引，例如标題title字段，可以隻取title的前10個字元索引，這樣的特性大大縮小了索引檔案的大小，但字首索引也有缺點，在order by和group by操作時失效。

create index idx_title on film(title(10));      

1 特點

值存在數組，用一個hash函數把key轉換成一個确定的記憶體位置，然後把value放在數組的該位置。使用 hash 自然會有哈希沖突可能，MySQL 采取拉鍊法解決。

Hash索引基于Hash表實作，隻有查詢條件精确比對Hash索引中的列時，才能夠使用到hash索引。對于Hash索引中的所有列，存儲引擎會為每行計算一個hashcode，Hash索引中存儲的就是hashcode。

例如一個維護了身份證号和姓名的表，根據身份證号查找對應名字，其hash索引如下：

比如我們想查ID_card_n4對應username：

将ID_card_n4通過hash函數算出A

按順序周遊，找到User4

四個ID_card_n值并不一定遞增，這樣即使增加新的User，速度也快，隻需在後追加。

當然缺點也很明顯，不是有序，是以hash索引做區間查詢速度很慢。比如要找身份證号在[ID_card_X, ID_card_Y]區間的所有使用者，就須全表掃描。

2 Hash索引的缺陷

不支援部分索引查找、範圍查找

哈希碼可能存在哈希沖突，如果hash 算法設計不好，碰撞過多，性能也會變差

索引存放的是hash值,是以僅支援 < = > 以及 IN

無法通過操作索引來排序，因為存放的時候會經過hash計算，但是計算的hash值和存放的不一定相等，是以無法排序

不能避免全表掃描，隻是由于在memory表裡支援非唯一值hash索引，即不同的索引鍵，可能存在相同hash值

因為哈希表是一種根據關鍵字直接通路記憶體存儲位置的資料結構 ，是以利用其原理的hash 索引，也就需要将所有資料檔案添加到記憶體，這就很耗記憶體

如果所有的查詢都是等值查詢，那麼hash确實快，但實際上範圍查找資料更多

隻能處理鍵值的全值比對查詢

Hash函數決定着索引鍵的大小

要使InnoDB或MyISAM支援哈希索引，可以通過僞哈希索引來實作，叫自适應哈希索引。

可通過增加一個字段，存儲hash值，将hash值建立索引，在插入和更新的時候，建立觸發器，自動添加計算後的hash到表裡。

哈希表這種結構适用于隻有等值查詢的場景，比如Memcached。

3 案例應用

假如有一個非常非常大的表，比如使用者登入時需要通過email檢索出使用者，如果直接在email列建索引，除了索引區間比對，還要進行字元串比對比對，email短還好，如果長的話這個查詢代價就比較大。

若此時，在email建立哈希索引，查詢以int查詢，性能就比字元串比對查詢快多了。

Hash 算法

建立哈希索引，首先就要標明雜湊演算法，《高性能MySQL》說到的CRC32算法。

INSERT UPDATE SELECT 操作

在表中添加hash值的字段：

ALTER TABLE `User` ADD COLUMN email_hash int unsigned NOT NULL DEFAULT 0;      

接下來就是在UPDATE和INSERT時，自動更新 

email_hash

 字段，通過觸發器實作：

DELIMITER |
CREATE TRIGGER user_hash_insert BEFORE INSERT ON `User` FOR EACH ROW BEGIN
SET NEW.email_hash=crc32(NEW.email);
END;
|
CREATE TRIGGER user_hash_update BEFORE UPDATE ON `User` FOR EACH ROW BEGIN
SET NEW.email_hash=crc32(NEW.email);
END;
|
DELIMITER ;      

這樣SELECT請求就會變成：

SELECT `email`, `email_hash` FROM `User` WHERE 
    email_hash = CRC32(“[email protected]”) 
            AND `email`= “[email protected]”;      

+----------------------------+------------+
| email                      | email_hash |
+----------------------------+------------+
| [email protected]             | 2765311122 |
+----------------------------+------------+
      

AND email = "[email protected]"

 是為了防止哈希碰撞時資料不準确。