mysql hash索引

2024-07-24 12:32:19

字體：大中小

供稿：網(wǎng)友

今天研究下mysql中索引，首先我應(yīng)該知道的是，mysql中不同存儲(chǔ)引擎的索引工作方式不一樣，并且不是所有的存儲(chǔ)引擎都支持所有類型的索引。即使多個(gè)存儲(chǔ)引擎支持同一種類型的索引，那么他們的實(shí)現(xiàn)原理也是不同的。不同的引擎對(duì)于索引有不同的支持：Innodb和MyISAM默認(rèn)的索引是 Btree索引；而Mermory默認(rèn)的索引是Hash索引。
mysql中主要有哈希索引（hash index)、B-Tree索引，全文索引、以及空間數(shù)據(jù)索引（R-Tree)；
今天主要講下mysql中的哈希索引（hash index)
它是基于哈希表實(shí)現(xiàn)，只有精確匹配索引所有列的查詢才有效，對(duì)于每一行數(shù)據(jù)，存儲(chǔ)引擎都會(huì)對(duì)所有的索引列計(jì)算一個(gè)哈希碼（hash code)，哈希碼是一個(gè)較小的值，大部分情況下不同的鍵值的行計(jì)算出來(lái)的哈希碼是不同的，但是也會(huì)有例外，就是說(shuō)不同列值計(jì)算出來(lái)的hash值一樣的（即所謂的hash沖突），哈希索引將所有的哈希碼存儲(chǔ)在索引中，同時(shí)在哈希表中保存指向每一個(gè)數(shù)據(jù)行的指針，hash很適合做索引，為某一列或幾列建立hash索引，就會(huì)利用這一列或幾列的值通過(guò)一定的算法計(jì)算出一個(gè)hash值，對(duì)應(yīng)一行或幾行數(shù)據(jù)。

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

（編輯：武林網(wǎng)）

上一篇：MYSQL Can t get hostname for your address

下一篇：MySQL double write