mysql hash索引
今天研究下
mysql中索引，首先我應(yīng)該知道的是，mysql中不同存儲引擎的索引工作方式不一樣，并且不是所有的存儲引擎都支持所有類型的索引。即使多個存儲引擎支持同一種類型的索引，那么他們的實現(xiàn)原理也是不同的。不同的引擎對于索引有不同的支持：
Innodb和MyISAM默認的索引是Btree索引；而Mermory默認的索引是Hash索引。
mysql中主要有哈希索引（hash index)、B-Tree索引，全文索引、以及空間數(shù)據(jù)索引（R-Tree)；
今天主要講下mysql中的哈希索引（hash index)
它是基于哈希表實現(xiàn)，只有精確匹配索引所有列的查詢才有效，對于每一行數(shù)據(jù)，存儲引擎都會對所有的索引列計算一個哈希碼（hash code)，哈希碼是一個較小的值，大部分情況下不同的鍵值的行計算出來的哈希碼是不同的，但是也會有例外，就是說不同列值計算出來的hash值一樣的（即所謂的hash沖突），哈希索引將所有的哈希碼存儲在索引中，同時在哈希表中保存指向每一個數(shù)據(jù)行的指針，hash很適合做索引，為某一列或幾列建立hash索引，就會利用這一列或幾列的值通過一定的算法計算出一個hash值，對應(yīng)一行或幾行數(shù)據(jù)。
hash 索引的實現(xiàn)原理如下圖：
針對上圖的理解：
keys：代表創(chuàng)建索引的列值；
buckets： 就是計算出來的hash值和對應(yīng)的數(shù)據(jù)的物理位置組成的hash表；
entries：就是代表具體的數(shù)據(jù)行；
創(chuàng)建hash索引后，會為每個鍵值通過特定的算法計算出一個哈希碼（hash code)，需要注意的是不同的鍵值計算出來的hash值可能是相同的，例上圖上的 John Smith 和Sandra Dee算出來的hash值都是152，然后找到hash值為152在hash表中的存儲數(shù)據(jù)的物理位置，這個位置對應(yīng)著兩條數(shù)據(jù)也(就是John Smith 521-1234 和Sandra Dee 521-9655)，然后再次遍歷這兩條數(shù)據(jù)，找到需要的數(shù)據(jù)，這就解釋了為啥hash沖突嚴重了，hash索引效率降低的原因。
hash索引檢索數(shù)據(jù)的過程（摘雜網(wǎng)絡(luò)）
當我們?yōu)槟骋涣谢蚰硯琢薪ash索引時（目前就只有MEMORY引擎顯式地支持這種索引），會在硬盤上生成類似如下的文件：
|
hash值
|
存儲地址
|
|
1db54bc745a1
|
77#45b5
|
|
4bca452157d4
|
76#4556,77#45cc…
|
…
hash值即為通過特定算法由指定列數(shù)據(jù)計算出來，存儲地址即為所在數(shù)據(jù)行存儲在硬盤上的地址（也有可能是其他存儲地址，其實MEMORY會將hash表導入內(nèi)存）。
這樣，當我們進行WHERE age = 18 時，會將18通過相同的算法計算出一個hash值==>在hash表中找到對應(yīng)的儲存地址==>根據(jù)存儲地址取得數(shù)據(jù)==>最后一步確定這行數(shù)據(jù)是否是需要查詢的數(shù)據(jù)。
所以，每次查詢時都要遍歷hash表，直到找到對應(yīng)的hash值，數(shù)據(jù)量大了之后，hash表也會變得龐大起來，性能下降，遍歷耗時增加；
MySQLhash索引的適用情況：
檢索時不需要類似B+樹那樣從根節(jié)點到葉子節(jié)點逐級查找，只需一次哈希算法即可立刻定位到相應(yīng)的位置，速度非?？欤枪Ｋ饕贿m合某些特定的場景，而一旦適合哈希索引，則它帶來的性能提升非常明顯，除了memory引擎外，NDB引擎也支持唯一哈希索引；
innodb引擎有一個特殊的功能叫做自適應(yīng)哈希索引，當innodb注意到某些索引值被使用的非常頻繁時，它會在內(nèi)存中基于btree索引之上再創(chuàng)建一個哈希索引，這樣就讓btree索引也具有哈希索引的一些優(yōu)點，比如：快速的哈希查找，這是一個全自動的，內(nèi)部的行為，用戶無法控制或者配置，不過如果有必要，可以選擇關(guān)閉這個功能（innodb_adaptive_hash_index=OFF，默認為ON）。
正是因為hash表在處理較小數(shù)據(jù)量時具有無可比擬的素的優(yōu)勢，所以hash索引很適合做緩存（內(nèi)存數(shù)據(jù)庫）。如mysql數(shù)據(jù)庫的內(nèi)存版本Memsql，使用量很廣泛的緩存工具Mencached，
NoSql數(shù)據(jù)庫redis等，都使用了hash索引這種形式。當然，不想學習這些東西的話Mysql的MEMORY引擎也是可以滿足這種需求的。
mysql hash索引的局限性：
（1）Hash 索引僅僅能滿足"=","IN"和"<=>"的等值查詢，不能使用范圍查詢。
由于 Hash 索引比較的是進行 Hash 運算之后的 Hash 值，所以它只能用于等值的過濾，不能用于基于范圍的過濾，因為經(jīng)過相應(yīng)的 Hash 算法處理之后的 Hash 值的大小關(guān)系，并不能保證和Hash運算前完全一樣。
（2）因為哈希索引并不是按照索引值順序存儲的，所以Hash 索引無法被用來避免數(shù)據(jù)的排序操作。 由于 Hash 索引中存放的是經(jīng)過 Hash 計算之后的 Hash 值，而且Hash值的大小關(guān)系并不一定和 Hash 運算前的鍵值完全一樣，所以數(shù)據(jù)庫無法利用索引的數(shù)據(jù)來避免任何排序運算；
（3）Hash 索引不能利用部分索引鍵查詢，也就是針對組合索引，不支持最左匹配原則
對于組合索引，Hash 索引在計算 Hash 值的時候是組合索引鍵合并后再一起計算 Hash 值，而不是單獨計算 Hash 值，所以通過組合索引的前面一個或幾個索引鍵進行查詢的時候，Hash 索引也無法被利用，也就是說，在數(shù)據(jù)列（A，B）上建立哈希索引，如果查詢只有數(shù)據(jù)列(where A=）是無法使用該索引的。
（4）Hash 索引在任何時候都不能避免表掃描。
前面已經(jīng)知道，Hash 索引是將索引鍵通過 Hash 運算之后，將 Hash運算結(jié)果的 Hash 值和所對應(yīng)的行指針信息存放于一個 Hash 表中，由于相同的列值計算出來的 Hash 值可能一樣的，所以即使取滿足某個 Hash 鍵值的數(shù)據(jù)的記錄條數(shù)，也無法從 Hash 索引中直接完成查詢，還是要通過訪問表中的實際數(shù)據(jù)進行相應(yīng)的比較，并得到相應(yīng)的結(jié)果。
（5）Hash 索引遇到大量Hash值相等的情況后性能并不一定就會比B-Tree索引高。
對于選擇性比較低的索引鍵（存在大量hash沖突，也就是大量重復值，可選擇率高代表選出來的值/去重的值 比較大），如果創(chuàng)建 Hash 索引，那么將會存在大量記錄指針信息和同一個 Hash 值相關(guān)聯(lián)。這樣要定位某一條記錄時就會非常麻煩，會浪費多次表數(shù)據(jù)的訪問，而造成整體性能低下。
(6) 哈希索引只包含哈希值和行指針，而不存儲字段值，所以不能使用索引中的值來避免讀取行（即不能使用哈希索引來做覆蓋索引掃描），不過，訪問內(nèi)存中的行的速度很快（因為memory引擎的數(shù)據(jù)都保存在內(nèi)存里），所以大部分情況下這一點對性能的影響并不明顯。
（7）如果哈希沖突很多的話，一些索引維護操作的代價也會很高。例如，如果在某個選擇性很低（哈希沖突很多）的列上建立哈希索引，那么當從表中刪除一行時，存儲引擎需要遍歷對應(yīng)哈希值的鏈表中的每一行，找到并刪除對應(yīng)的引用，沖突越多，代價越大。
總結(jié)： 如果hash鍵值沒有重復值，并且數(shù)據(jù)量較小時，通過hash索引檢索數(shù)據(jù)還是比btree索引快的，但是當哈希值大量重復且數(shù)據(jù)量非常大時，其檢索效率并沒有Btree索引高的。哈希索引只適合某些特定的場景，而一旦適合哈希索引，則它帶來的性能提升非常明顯的，因為它不會像btree索引那樣一級一級的去遍歷檢索得到數(shù)據(jù)。Hash索引結(jié)構(gòu)的特殊性，讓他的檢索效率非常高，索引的檢索可以一次定位，不像BTree索引需要從根節(jié)點到枝節(jié)點，最后才能訪問到葉節(jié)點這樣多次的I/O訪問，所以Hash索引的查詢效率要遠高于BTree索引。
