轉(zhuǎn)自：https://blog.csdn.net/chuangsun/article/details/78013537
關(guān)系型數(shù)據(jù)庫(kù)中挤渔，索引大多采用B/B+樹(shù)來(lái)作為存儲(chǔ)結(jié)構(gòu)，而全文搜索引擎的索引則主要采用hash的存儲(chǔ)結(jié)構(gòu)风题，這兩種數(shù)據(jù)結(jié)構(gòu)有什么區(qū)別判导？
如果是等值查詢(xún)，那么哈希索引明顯有絕對(duì)優(yōu)勢(shì)沛硅，因?yàn)橹恍枰?jīng)過(guò)一次算法即可找到相應(yīng)的鍵值眼刃；當(dāng)然了，這個(gè)前提是稽鞭，鍵值都是唯一的鸟整。如果鍵值不是唯一的，就需要先找到該鍵所在位置朦蕴，然后再根據(jù)鏈表往后掃描篮条，直到找到相應(yīng)的數(shù)據(jù)；
從示意圖中也能看到吩抓，如果是范圍查詢(xún)檢索涉茧，這時(shí)候哈希索引就毫無(wú)用武之地了，因?yàn)樵仁怯行虻逆I值疹娶，經(jīng)過(guò)哈希算法后伴栓，有可能變成不連續(xù)的了，就沒(méi)辦法再利用索引完成范圍查詢(xún)檢索雨饺；
同理钳垮，哈希索引也沒(méi)辦法利用索引完成排序，以及l(fā)ike ‘xxx%’ 這樣的部分模糊查詢(xún)（這種部分模糊查詢(xún)额港，其實(shí)本質(zhì)上也是范圍查詢(xún)）饺窿；
哈希索引也不支持多列聯(lián)合索引的最左匹配規(guī)則；
B+樹(shù)索引的關(guān)鍵字檢索效率比較平均移斩，不像B樹(shù)那樣波動(dòng)幅度大肚医，在有大量重復(fù)鍵值情況下绢馍，哈希索引的效率也是極低的，因?yàn)榇嬖谒^的哈希碰撞問(wèn)題
hash結(jié)構(gòu)的特點(diǎn)：檢索效率非常高肠套，索引的檢索可以一次到位舰涌，O(1)。B樹(shù)需要從根節(jié)點(diǎn)到枝節(jié)點(diǎn)你稚，最后才能到葉節(jié)點(diǎn)進(jìn)行多次I/O操作瓷耙，所以hash的效率遠(yuǎn)遠(yuǎn)高于B樹(shù)的效率。
那么為什么數(shù)據(jù)庫(kù)索引還是用B樹(shù)結(jié)構(gòu)呢入宦？
1哺徊、hash索引僅滿(mǎn)足“=”室琢、“IN”和“<=>”查詢(xún)乾闰，不能使用范圍查詢(xún)
因?yàn)閔ash索引比較的是經(jīng)常hash運(yùn)算之后的hash值，因此只能進(jìn)行等值的過(guò)濾盈滴，不能基于范圍的查找涯肩，因?yàn)榻?jīng)過(guò)hash算法處理后的hash值的大小關(guān)系，并不能保證與處理前的hash大小關(guān)系對(duì)應(yīng)巢钓。
2病苗、hash索引無(wú)法被用來(lái)進(jìn)行數(shù)據(jù)的排序操作
由于hash索引中存放的都是經(jīng)過(guò)hash計(jì)算之后的值，而hash值的大小關(guān)系不一定與hash計(jì)算之前的值一樣症汹，所以數(shù)據(jù)庫(kù)無(wú)法利用hash索引中的值進(jìn)行排序操作硫朦。
3、對(duì)于組合索引背镇，Hash 索引在計(jì)算 Hash 值的時(shí)候是組合索引鍵合并后再一起計(jì)算 Hash 值咬展，而不是單獨(dú)計(jì)算 Hash 值，所以通過(guò)組合索引的前面一個(gè)或幾個(gè)索引鍵進(jìn)行查詢(xún)的時(shí)候瞒斩，Hash 索引也無(wú)法被利用破婆。
4、Hash 索引遇到大量Hash值相等的情況后性能并不一定就會(huì)比B-Tree索引高胸囱。
對(duì)于選擇性比較低的索引鍵祷舀，如果創(chuàng)建 Hash 索引，那么將會(huì)存在大量記錄指針信息存于同一個(gè) Hash 值相關(guān)聯(lián)烹笔。這樣要定位某一條記錄時(shí)就會(huì)非常麻煩裳扯，會(huì)浪費(fèi)多次表數(shù)據(jù)的訪問(wèn)，而造成整體性能低下谤职。
（因此：鍵值重復(fù)率低的適合用B樹(shù)索引）
b-tree完全基于key的比較饰豺，和二叉樹(shù)相同的道理，相當(dāng)于建個(gè)排序后的數(shù)據(jù)集柬帕，使用二分法查找算法哟忍，實(shí)際上也非辰泼牛快，而且受數(shù)據(jù)量增長(zhǎng)影響非常小锅很。
B+樹(shù)索引和哈希索引的區(qū)別
轉(zhuǎn)自：https://www.cnblogs.com/bonelee/p/6224698.html
哈希文件也稱(chēng)為散列文件其馏，是利用哈希存儲(chǔ)方式組織的文件，亦稱(chēng)為直接存取文件爆安。它類(lèi)似于哈希表叛复，即根據(jù)文件中關(guān)鍵字的特點(diǎn)，設(shè)計(jì)一個(gè)哈希函數(shù)和處理沖突的方法扔仓，將記錄哈希到存儲(chǔ)設(shè)備上褐奥。
在哈希文件中，是使用一個(gè)函數(shù)（算法）來(lái)完成一種將關(guān)鍵字映射到存儲(chǔ)器地址的映射翘簇，根據(jù)用戶(hù)給出的關(guān)鍵字撬码，經(jīng)函數(shù)計(jì)算得到目標(biāo)地址，再進(jìn)行目標(biāo)的檢索版保。
轉(zhuǎn)自：http://imysql.com/2016/01/06/mysql-faq-different-between-btree-and-hash-index.shtml
B+樹(shù)索引和哈希索引的區(qū)別
一個(gè)經(jīng)典的B+樹(shù)索引數(shù)據(jù)結(jié)構(gòu)見(jiàn)下圖：
(圖片源自網(wǎng)絡(luò))
B+樹(shù)是一個(gè)平衡的多叉樹(shù)呜笑，從根節(jié)點(diǎn)到每個(gè)葉子節(jié)點(diǎn)的高度差值不超過(guò)1，而且同層級(jí)的節(jié)點(diǎn)間有指針相互鏈接彻犁。
在B+樹(shù)上的常規(guī)檢索叫胁，從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的搜索效率基本相當(dāng)，不會(huì)出現(xiàn)大幅波動(dòng)汞幢，而且基于索引的順序掃描時(shí)驼鹅，也可以利用雙向指針快速左右移動(dòng)，效率非常高森篷。因此输钩，B+樹(shù)索引被廣泛應(yīng)用于數(shù)據(jù)庫(kù)、文件系統(tǒng)等場(chǎng)景疾宏。
而哈希索引的示意圖則是這樣的：
(圖片源自網(wǎng)絡(luò))
簡(jiǎn)單地說(shuō)张足，哈希索引就是采用一定的哈希算法，把鍵值換算成新的哈希值坎藐，檢索時(shí)不需要類(lèi)似B+樹(shù)那樣從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)逐級(jí)查找为牍，只需一次哈希算法即可立刻定位到相應(yīng)的位置，速度非逞意桑快碉咆。
從上面的圖來(lái)看，B+樹(shù)索引和哈希索引的明顯區(qū)別是：
如果是等值查詢(xún)蛀恩，那么哈希索引明顯有絕對(duì)優(yōu)勢(shì)疫铜，因?yàn)橹恍枰?jīng)過(guò)一次算法即可找到相應(yīng)的鍵值；當(dāng)然了双谆，這個(gè)前提是壳咕，鍵值都是唯一的席揽。如果鍵值不是唯一的，就需要先找到該鍵所在位置谓厘，然后再根據(jù)鏈表往后掃描幌羞，直到找到相應(yīng)的數(shù)據(jù)；
從示意圖中也能看到竟稳，如果是范圍查詢(xún)檢索属桦，這時(shí)候哈希索引就毫無(wú)用武之地了，因?yàn)樵仁怯行虻逆I值他爸，經(jīng)過(guò)哈希算法后聂宾，有可能變成不連續(xù)的了，就沒(méi)辦法再利用索引完成范圍查詢(xún)檢索诊笤；
同理系谐，哈希索引也沒(méi)辦法利用索引完成排序，以及l(fā)ike ‘xxx%’ 這樣的部分模糊查詢(xún)（這種部分模糊查詢(xún)盏混，其實(shí)本質(zhì)上也是范圍查詢(xún)）蔚鸥；
哈希索引也不支持多列聯(lián)合索引的最左匹配規(guī)則；
B+樹(shù)索引的關(guān)鍵字檢索效率比較平均许赃，不像B樹(shù)那樣波動(dòng)幅度大，在有大量重復(fù)鍵值情況下馆类，哈希索引的效率也是極低的混聊，因?yàn)榇嬖谒^的哈希碰撞問(wèn)題。
后記
通常乾巧，B+樹(shù)索引結(jié)構(gòu)適用于絕大多數(shù)場(chǎng)景句喜，像下面這種場(chǎng)景用哈希索引才更有優(yōu)勢(shì)：
在HEAP表中，如果存儲(chǔ)的數(shù)據(jù)重復(fù)度很低（也就是說(shuō)基數(shù)很大）沟于，對(duì)該列數(shù)據(jù)以等值查詢(xún)?yōu)橹骺任福瑳](méi)有范圍查詢(xún)、沒(méi)有排序的時(shí)候旷太，特別適合采用哈希索引
例如這種SQL：
SELECT … FROM t WHERE C1 = ?; — 僅等值查詢(xún)
在大多數(shù)場(chǎng)景下展懈，都會(huì)有范圍查詢(xún)、排序供璧、分組等查詢(xún)特征存崖，所以數(shù)據(jù)庫(kù)使用B+樹(shù)索引。
