MySQL中的hash index
- 一、散串列（哈希表）
- 二、Hash 索引
- 三、InnoDB 中的自適應哈希索引
- 四、總結
題外話
前幾天有人問到MongoDB的hash分片是怎么實作的，當時記憶有些模糊，聯想到了mysql的hash索引，故簡單整理了此文，MongoDB的hash分片介紹可參考我另一文章：https://blog.csdn.net/tah_001/article/details/108690215
一、散串列（哈希表）
散串列（Hash table，也叫哈希表），是依據關鍵碼值(Key value)而直接進行訪問的資料結構，也就是說，它通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度，這個映射函式叫做散列函式，存放記錄的陣列叫做散串列，
散串列,它是基于高速存取的角度設計的，也是一種典型的“空間換時間”的做法，顧名思義，該資料結構能夠理解為一個線性表，可是當中的元素不是緊密排列的，而是可能存在空隙，
散列方法的主要思想是根據結點的關鍵碼值來確定其存盤地址：以關鍵碼值K為自變數，通過一定的函式關系h(K)(稱為散列函式)，計算出對應的函式值來，把這個值解釋為結點的存盤地址，將結點存入到此存盤單元中，檢索時，用同樣的方法計算地址，然后到相應的單元里去取要找的結點，通過散列方法可以對結點進行快速檢索，散列（hash，也稱“哈希”）是一種重要的存盤方式，也是一種常見的檢索方法，
二、Hash 索引
哈希索引（hash index）基于哈希表實作，只有精確匹配索引所有列的查詢才有效，對于每一行資料，存盤引擎都會對所有的索引列計算一個哈希碼，哈希碼是一個較小的值，并且不同鍵值的行計算出來的哈希碼也不一樣，哈希碼索引將所有的哈希碼存盤在索引中，同時在哈希表中保存指向每個資料行的指標，
因為索引自身只需存盤對應的哈希值，所以索引的結構十分緊湊，這也讓哈希索引查找的速度非常快，然而，哈希索引也有他的限制：
1）哈希索引只包含哈希值和行指標，而不存盤欄位值，所以不能使用索引中的值來避免讀取行，不過，訪問記憶體中的行的速度很快，所以大部分情況下這一點對性能的影響并不明顯，
2）哈希索引資料并不是按照索引值順序存盤的，所以也就無法用于排序
3）哈希索引也不支持部分索引列匹配查找，因為哈希索引始終是使用索引列的全部內容來計算哈希值的，
4）哈希索引只支持等值比較查詢，包括=、IN()、<=>、也不支持任何范圍查詢，
5）訪問哈希索引的資料非常快，除非有很多哈希沖突（不同的索引列值卻有相同的哈希值），當出現哈希沖突的時候，存盤引擎必須遍歷鏈表中所有的行指標，逐行進行比較，直到找到所有符合條件的行，
6）如果哈希沖突很多的話，一些索引維護操作的代價也會很高，例如，如果在某個選擇性很低（哈希沖突很多）的列上建立哈希索引，那么當從表中洗掉一行時，存盤引擎需要遍歷對應哈希值的鏈表中的每一行，找到并洗掉對應的參考，沖突越多，代價越大，
因為這些限制，哈希索引只適用于某些特定的場合，而一旦適合哈希索引，則它帶來的性能提升將非常顯著，舉個例子，在資料倉庫應用中有一種經典的“星型” schema，需要關聯很多查找表，哈希索引就非常適合查找表的需求，
除了Memory引擎外，NDB集群引擎也支持唯一哈希索引，且在NDB集群引擎中作用非常特殊，
三、InnoDB 中的自適應哈希索引
InnoDB 引擎有一個特殊額功能叫做“自適應哈希索引”，當 InnoDB注意到某些索引值被使用得非常頻繁時，它會在記憶體中基于B-Tree索引之上再創建一個哈希索引，這樣就讓B-Tree索引頁具有哈希索引的一些優點，比如快速的哈希查找，這是一個完全自動的、內部的行為，用戶無法控制或者配置，不過若果有必要，完全可以關閉該功能，
四、總結
勺ò干以知道hash index的效率非常高，但在mysql中限制也很多，所以我們應按實際情況合理使用；最后借鑒一匿名網友生動的描述，理解一下hash演算法：（借鑒地址：https://zhidao.baidu.com/question/548095906.html）
假如我們有很多的小豬，每個4102的體重都不一樣，假設體重分布比較平均(我們考慮到公斤級別)，我們按照體重來分,劃分成100個小豬圈，
然后把每個小豬，按照體重趕進各自的豬圈里，記錄檔案， 好了，如果我們要找某個小豬怎么辦呢？我們需要每個豬圈，每個小豬的比對嗎？
當然不需要了， 我們先看看要找的這個小豬的體重，然后就找到了對應的豬圈了，
在這個豬圈里的小豬的數量就相對很少了，
我們在這個豬圈里就可以相對快的找到我們要找到的那個小豬了， 對應于hash演算法，
就是按照hashcode分配不同的豬圈，將hashcode相同的豬放到一個豬圈里，
查找的時候，先找到hashcode對應的豬圈，然后在逐個比較里面的小豬， 所以問題的關鍵就是建造多少個豬圈比較合適， 如果每個小豬的體重全部不同（考慮到毫克級別)，每個都建一個豬圈，那么我們可以最快速度的找到這頭豬，缺點就是，建造那么多豬圈的費用有點太高了， 如果我們按照10公斤級別進行劃分，那么建造的豬圈只有幾個吧，那么每個圈里的小豬就很多了，我1653們雖然可以很快的找到豬圈，但從這個豬圈里逐個確定那頭小豬也是很累的， 所以，好的hashcode，可以根據實際情況，根據具體的需求，在時間成本(更多的豬圈，更快的速度)和空間本(更少的豬圈，更低的空間需求)之間平衡，
哎喲，不錯噢！ - - - - - - 歡迎指出有誤的地方以及補充更好的方法
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/99445.html
標籤：AI
上一篇：410c光流定位夠用嗎？
下一篇：短信攔截