第二章sql性能優(yōu)化篇18講25hash索引底層原理

2019-08-07SQL必知必 進(jìn)入課06:49我們上節(jié)課講解了B+樹的原理，今天我們來學(xué)習(xí)下Hash的原理和使用。Hash本身是一個函數(shù)，又被稱為散列函數(shù)，它可以幫助我們大幅提升檢索數(shù)據(jù)的效率。打個比方，ash就好像一個智能前臺，你只要告訴它想要查找的人的姓名，它就會告訴你那個人坐在哪個位置，只需要一次交互就可以完成查找，效率非常高。大名鼎鼎的MD5就是Hash函數(shù)的一種。Hash算法是通過某種確定性的算法（比如MD5、SHA1、SHA2、SHA3）將輸入轉(zhuǎn)變?yōu)橹恍枰寣Ψ桨袶ash函數(shù)計(jì)算得到的結(jié)果告訴你即可，然后在本地同樣對文件進(jìn)行Hash函數(shù)的運(yùn)算，最后通過比較這兩個Hash函數(shù)的結(jié)果是否相同，就可以知道這兩個文件是否Hash動手寫程序統(tǒng)計(jì)一下Hash了解MySQL中的HashHash索引和BHash我們知道Python的數(shù)據(jù)結(jié)構(gòu)中有數(shù)組和字典兩種，其中數(shù)組檢索數(shù)據(jù)類似于全表掃描，需要對整個數(shù)組的內(nèi)容進(jìn)行檢索；而字典是由Hash表實(shí)現(xiàn)的，存儲的是key-value值，對于Hash11000010000復(fù)制代碼import#result=foriin#foriintemp=print('檢索時間',time_end-檢索時間為1.2436728477478027秒2HashPython10000素，然后檢索這10000個數(shù)據(jù)，最后再統(tǒng)計(jì)一下時間。代碼如下：復(fù)制代碼import#result=foriinresult[i]=#foriintemp=檢索時間為0.0019941329956054688你能看到Hash方式檢索差不多用了2毫秒的時間，檢索效率提升得非常明顯。這是因?yàn)镠ash只需要一步就可以找到對應(yīng)的取值，算法復(fù)雜度為O(1)，而數(shù)組檢索數(shù)據(jù)的算法復(fù)雜度為O(n)。MySQLHash采用Hash進(jìn)行檢索效率非常高，基本上一次檢索就可以找到數(shù)據(jù)，而B+樹需要自頂向下依次查找，多次訪問節(jié)點(diǎn)才能找到數(shù)據(jù)，中間需要多次I/O操作，從效率來說Hash比B+我們來看下Hash鍵值key通過Hash映射找到桶bucket。在這里桶（bucket）指的是一個能存儲一條或一行，形成鏈表結(jié)構(gòu)，當(dāng)遇到Hash沖突時，會在桶中進(jìn)行鍵值的查找。那么什么是HashHash4HashHash1632MD53232MD5我們模擬一下Hash索引。關(guān)鍵字如下所示，每個字母的內(nèi)部編碼為字母的序號，比如01，Y258-11（從前向后）HashHashB我們之前講到過B+樹索引的結(jié)構(gòu)，Hash索引結(jié)構(gòu)和B+樹的不同，因此在索引使用上也Hash索引不能進(jìn)行范圍查詢，而B+樹可以。這是因?yàn)镠ash索引指向的數(shù)據(jù)是無序的，而B+樹的葉子節(jié)點(diǎn)是個有序的鏈表。Hash索引不支持聯(lián)合索引的最左側(cè)原則（即聯(lián)合索引的部分索引無法使用），而B+樹可以。對于聯(lián)合索引來說，Hash索引在計(jì)算Hash值的時候是將索引鍵合并后再一起計(jì)算Hash值，所以不會針對每個索引單獨(dú)計(jì)算Hash值。因此如果用到聯(lián)合索引的一Hash索引不支持ORDERBY排序，因?yàn)镠ash索引指向的數(shù)據(jù)是無序的，因此無法起到排序優(yōu)化的作用，而B+樹索引數(shù)據(jù)是有序的，可以起到對該字段ORDERBY排序優(yōu)化的作用。同理，我們也無法用Hash索引進(jìn)行模糊查詢，而B+樹使用LIKE進(jìn)行模糊查詢的時候，LIKE后面前模糊查詢（比如%開頭）的話就可以起到優(yōu)化作用。對于等值查詢來說，通常Hash索引的效率更高，不過也存在一種情況，就是索引列的重復(fù)值如果很多，效率就會降低。這是因?yàn)橛龅紿ash沖突時，需要遍歷桶中的行指針來進(jìn)行比較，找到查詢的關(guān)鍵字，非常耗時。所以，Hash索引通常不會用到重復(fù)值多的列上，比如列庫中BHash型（Key-Value）數(shù)據(jù)庫中，Redis存儲的核心就是Hash另外MySQL中的Memory存儲引擎支持Hash存儲，如果我們需要用到查詢的臨時表時，就可以選擇Memory存儲引擎，把某個字段設(shè)置為Hash索引，比如字符串類型的字Hash等值查詢的時候，采用Hash索引是個不錯的選擇。另外MySQL的InnoDB存儲引擎還有個“自適應(yīng)Hash索引”的功能，就是當(dāng)某個索引BHashB也具備了Hash索引的優(yōu)點(diǎn)。今天的內(nèi)容到這里就結(jié)束了，我留兩道思考題吧。查找某個固定值時Hash索引比B+樹更快，為什么MySQL還要采用B+樹的存儲索引呢？另外，當(dāng)兩個關(guān)鍵字的Hash值相同時?上一 下一 21HashBMySQLB呢？另外，當(dāng)兩個關(guān)鍵字的Hash值相同時會發(fā)生什么？11老師，BLIKElikexxmysql查詢中存在著很多范圍查詢、orderby的場景，在這些場景下，B+樹的性能好于Ha能不能請老師分別推薦一下學(xué)習(xí)MySQL，Oracle，sqlServer作者回復(fù):可以看下關(guān)于MySQL高性能優(yōu)化的書籍，如果是數(shù)據(jù)庫初學(xué)者也可以先從SQLServer開始，畢竟微軟的產(chǎn)