導(dǎo)讀

在MySQL里常用的索引數(shù)據(jù)結(jié)構(gòu)有B+樹索引和哈希索引兩種，我們來看下這兩種索引數(shù)據(jù)結(jié)構(gòu)的區(qū)別及其不同的應(yīng)用建議。

二者區(qū)別

備注：先說下，?在MySQL文檔里，實際上是把B+樹索引寫成了BTREE?，例如像下面這樣的寫法：

CREATE TABLE t(

aid int unsigned not null auto_increment,

userid int unsigned not null default 0,

username varchar(20) not null default ‘’,

detail varchar(255) not null default ‘’,

primary key(aid),

unique key(uid) USING?BTREE?,

key (username(12)) USING?BTREE?—?此處 uname 列只創(chuàng)建了最左12個字符長度的部分索引

)engine=InnoDB;

一個經(jīng)典的?B+樹索引數(shù)據(jù)結(jié)構(gòu)?見下圖：

B+樹是一個平衡的多叉樹，從根節(jié)點到每個葉子節(jié)點的高度差值不超過1，而且同層級的節(jié)點間有指針相互鏈接。

在B+樹上的常規(guī)檢索，從根節(jié)點到葉子節(jié)點的搜索效率基本相當(dāng)，不會出現(xiàn)大幅波動，而且基于索引的順序掃描時，也可以利用雙向指針快速左右移動，效率非常高。

因此，B+樹索引被廣泛應(yīng)用于數(shù)據(jù)庫、文件系統(tǒng)等場景。順便說一下，xfs文件系統(tǒng)比ext3/ext4效率高很多的原因之一就是，它的文件及目錄索引結(jié)構(gòu)全部采用B+樹索引，而ext3/ext4的文件目錄結(jié)構(gòu)則采用Linked list, hashed B-tree、Extents/Bitmap等索引數(shù)據(jù)結(jié)構(gòu)，因此在高I/O壓力下，其IOPS能力不如xfs。

詳細(xì)可參見：

https://en.wikipedia.org/wiki/Ext4https://en.wikipedia.org/wiki/XFS

而?哈希索引的示意圖?則是這樣的：

簡單地說，?哈希索引就是采用一定的哈希算法?，把鍵值換算成新的哈希值，檢索時不需要類似B+樹那樣從根節(jié)點到葉子節(jié)點逐級查找，只需一次哈希算法即可立刻定位到相應(yīng)的位置，速度非常快。

從上面的圖來看，B+樹索引和哈希索引的明顯區(qū)別是：

• 如果是等值查詢，那么哈希索引明顯有絕對優(yōu)勢，因為只需要經(jīng)過一次算法即可找到相應(yīng)的鍵值；當(dāng)然了，這個前提是，鍵值都是唯一的。如果鍵值不是唯一的，就需要先找到該鍵所在位置，然后再根據(jù)鏈表往后掃描，直到找到相應(yīng)的數(shù)據(jù)；

• 從示意圖中也能看到，?如果是范圍查詢檢索，這時候哈希索引就毫無用武之地了?，因為原先是有序的鍵值，經(jīng)過哈希算法后，有可能變成不連續(xù)的了，就沒辦法再利用索引完成范圍查詢檢索；

• 同理，?哈希索引也沒辦法利用索引完成排序?，以及l(fā)ike ‘xxx%’ 這樣的部分模糊查詢（這種部分模糊查詢，其實本質(zhì)上也是范圍查詢）；

• 哈希索引也不支持多列聯(lián)合索引的最左匹配規(guī)則；

• B+樹索引的關(guān)鍵字檢索效率比較平均，不像B樹那樣波動幅度大，?在有大量重復(fù)鍵值情況下，哈希索引的效率也是極低的，因為存在所謂的哈希碰撞問題?。

后記

在MySQL中，只有HEAP/MEMORY引擎表才能顯式支持哈希索引（NDB也支持，但這個不常用），InnoDB引擎的自適應(yīng)哈希索引（adaptive hash index）不在此列，因為這不是創(chuàng)建索引時可指定的。

還需要注意到：HEAP/MEMORY引擎表在mysql實例重啟后，數(shù)據(jù)會丟失。

通常，B+樹索引結(jié)構(gòu)適用于絕大多數(shù)場景，像下面這種場景用哈希索引才更有優(yōu)勢：

在HEAP表中，如果存儲的數(shù)據(jù)重復(fù)度很低（也就是說基數(shù)很大），對該列數(shù)據(jù)以等值查詢?yōu)橹?#xff0c;沒有范圍查詢、沒有排序的時候，特別適合采用哈希索引

例如這種SQL：SELECT … FROM t WHERE C1 = ?; — 僅等值查詢

在大多數(shù)場景下，都會有范圍查詢、排序、分組等查詢特征，用B+樹索引就可以了。

總結(jié)

以上是生活随笔為你收集整理的数据库：B+树索引和Hash索引得区别的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。