MySQL 索引結構 hash 有序數組

除了最常見的樹形索引結構，Hash索引也有它的獨到之處。

Hash演算法

• Hash本身是一種函數，又被稱為散列函數。

• 它的思路很簡單：將key放在數組裡，用一個hash演算法把不同的key轉換成一個確定的value，然後放在這個數組的指定位置

  相同的輸入永遠可以得到相同的輸出

• 具體的演算法有MD5、SHA1、SHA2、SHA3

• Hash衝突：不同的key得到了相同的value

  當出現Hash衝突，可以在衝突發生的位置跟一個鏈表

Hash索引

索引使用的數據結構的特性會讓索引也具有不同的特性：

• Hash索引只適用於等值查詢的場景，區間查詢速度很慢

  因為經過hash函數處理後，即便是原本有序的輸入，最後存放的位置也會變為無序的。

• 檢索速度很快

  索引檢索一次到位，而不需要想B+樹那樣從根節點訪問到葉子節點。不過在有大量重覆值得情況下，hash索引的效率極低，因為要頻發地處理Hash衝突。

• 無法完成排序，模糊查詢

  因為它們本質上是範圍查詢

• 不支持多列聯合索引的最左匹配原則

  對於Hash索引的聯合索引，是將聯合索引欄位值相捆綁然後計算Hash值的，無法利用對單一欄位的Hash值

Hash索引的用途：

• Hash索引更多地使用在鍵值型的資料庫中，比如Redis

• MySQL的Memory存儲引擎支持Hash存儲

  如果我們需要用到查詢的臨時表時，就可以選擇 Memory 存儲引擎，把某個欄位設置為 Hash 索引，比如字元串類型的欄位，進行 Hash 計算之後長度可以縮短到幾個位元組。當欄位的重覆度低，而且經常需要進行等值查詢的時候，採用 Hash 索引是個不錯的選擇

• InnoDB自適應Hash索引

  當某個索引值使用非常頻繁的時候，它會在 B+ 樹索引的基礎上再創建一個 Hash 索引，這樣讓 B+ 樹也具備了 Hash 索引的優點。

有序數組

如果我們使用有序數據作為索引結構的話，那麼

• 等值查詢和範圍查詢的性能都十分優秀
• 但是插入和刪除的成本太大

因此有序數組的結構只適合靜態存儲引擎，如果我們要存儲以某種有序編號為序的不輕易增刪的歷史數據，我們可以使用有序數組作為索引結構。