在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)典的BTREE索引數(shù)據(jù)結(jié)構(gòu)見下圖：

1.B-Tree索引

B-Tree 索引是 MySQL 數(shù)據(jù)庫中使用最為頻繁的索引類型，除了 Archive 存儲引擎之外的其他所有的存儲引擎都支持 B-Tree 索引。

不僅僅在 MySQL 中是如此，實際上在其他的很多數(shù)據(jù)庫管理系統(tǒng)中B-Tree 索引也同樣是作為最主要的索引類型，這主要是因為B-Tree 索引的存儲結(jié)構(gòu)在數(shù)據(jù)庫的數(shù)據(jù)檢索中有非常優(yōu)異的表現(xiàn)。

一般來說， MySQL 中的 B-Tree 索引的物理文件大多都是以 Balance Tree 的結(jié)構(gòu)來存儲的，也就是所有實際需要的數(shù)據(jù)都存放于 Tree 的 Leaf Node ，而且到任何一個 Leaf Node 的最短路徑的長度都是完全相同的，所以我們大家都稱之為 B-Tree 索引。

當(dāng)然，可能各種數(shù)據(jù)庫（或 MySQL 的各種存儲引擎）在存放自己的 B-Tree 索引的時候會對存儲結(jié)構(gòu)稍作改造。

如 Innodb 存儲引擎的 B-Tree 索引實際使用的存儲結(jié)構(gòu)實際上是 B+Tree ，也就是在 B-Tree 數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上做了很小的改造，在每一個Leaf Node 上面出了存放索引鍵的相關(guān)信息之外，還存儲了指向與該 Leaf Node 相鄰的后一個 LeafNode 的指針信息，這主要是為了加快檢索多個相鄰 Leaf Node 的效率考慮。

B+樹有如下特點(diǎn)：

• B+樹是一個平衡的多叉樹，從根節(jié)點(diǎn)到每個葉子節(jié)點(diǎn)的高度差值不超過1，而且同層級的節(jié)點(diǎn)間有指針相互鏈接。
• 在B+樹上的常規(guī)檢索，從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的搜索效率基本相當(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/Ext4
https://en.wikipedia.org/wiki/XFS

在 Innodb 存儲引擎中，存在兩種不同形式的索引，一種是 Cluster 形式的主鍵索引（ Primary Key ），另外一種則是和其他存儲引擎（如 MyISAM 存儲引擎）存放形式基本相同的普通 B-Tree 索引，這種索引在 Innodb 存儲引擎中被稱為 Secondary Index。

下面我們通過圖示來針對這兩種索引的存放 形式做一個比較。

圖示中左邊為 Clustered 形式存放的 Primary Key ，右側(cè)則為普通的 B-Tree 索引。兩種 Root Node 和 Branch Nodes 方面都還是完全一樣的。而 Leaf Nodes 就出現(xiàn)差異了。

在 Prim中， Leaf Nodes 存放的是表的實際數(shù)據(jù)，不僅僅包括主鍵字段的數(shù)據(jù)，還包括其他字段的數(shù)據(jù)據(jù)以主鍵值有序的排列。

而 Secondary Index 則和其他普通的 B-Tree 索引沒有太大的差異，Leaf Nodes 出了存放索引鍵 的相關(guān)信息外，還存放了 Innodb 的主鍵值。

所以，在 Innodb 中如果通過主鍵來訪問數(shù)據(jù)效率是非常高的，而如果是通過 Secondary Index 來訪問數(shù)據(jù)的話， Innodb 首先通過 Secondary Index 的相關(guān)信息，通過相應(yīng)的索引鍵檢索到 Leaf Node之后，需要再通過 Leaf Node 中存放的主鍵值再通過主鍵索引來獲取相應(yīng)的數(shù)據(jù)行。

MyISAM 存儲引擎的主鍵索引和非主鍵索引差別很小，只不過是主鍵索引的索引鍵是一個唯一且非空 的鍵而已。

而且 MyISAM 存儲引擎的索引和 Innodb 的 Secondary Index 的存儲結(jié)構(gòu)也基本相同，主要的區(qū)別只是 MyISAM 存儲引擎在 Leaf Nodes 上面出了存放索引鍵信息之外，再存放能直接定位到 MyISAM 數(shù)據(jù)文件中相應(yīng)的數(shù)據(jù)行的信息（如 Row Number ），但并不會存放主鍵的鍵值信息。

2.Hash索引

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

Hash 索引結(jié)構(gòu)的特殊性，其檢索效率非常高，索引的檢索可以一次定位，不像B-Tree 索引需要從根節(jié)點(diǎn)到枝節(jié)點(diǎn)，最后才能訪問到頁節(jié)點(diǎn)這樣多次的IO訪問，所以 Hash 索引的查詢效率要遠(yuǎn)高于 B-Tree 索引。

可能很多人又有疑問了，既然 Hash 索引的效率要比 B-Tree 高很多，為什么大家不都用 Hash 索引而還要使用 B-Tree 索引呢？

任何事物都是有兩面性的，Hash 索引也一樣，雖然 Hash 索引效率高，但是 Hash 索引本身由于其特殊性也帶來了很多限制和弊端，主要有以下這些應(yīng)用。

1.Hash 索引僅僅能滿足"=",“IN"和”<=>"查詢，不能使用范圍查詢。

由于 Hash 索引比較的是進(jìn)行 Hash 運(yùn)算之后的 Hash 值，所以它只能用于等值的過濾，不能用于基于范圍的過濾，因為經(jīng)過相應(yīng)的 Hash 算法處理之后的 Hash 值的大小關(guān)系，并不能保證和Hash運(yùn)算前完全一樣。

2.Hash 索引無法被用來避免數(shù)據(jù)的排序操作。

由于 Hash 索引中存放的是經(jīng)過 Hash 計算之后的 Hash 值，而且Hash值的大小關(guān)系并不一定和 Hash 運(yùn)算前的鍵值完全一樣，所以數(shù)據(jù)庫無法利用索引的數(shù)據(jù)來避免任何排序運(yùn)算；

3.Hash 索引不能利用部分索引鍵查詢。

對于組合索引，Hash 索引在計算 Hash 值的時候是組合索引鍵合并后再一起計算 Hash 值，而不是單獨(dú)計算 Hash 值，所以通過組合索引的前面一個或幾個索引鍵進(jìn)行查詢的時候，Hash 索引也無法被利用。

4.Hash 索引在任何時候都不能避免表掃描。

前面已經(jīng)知道，Hash 索引是將索引鍵通過 Hash 運(yùn)算之后，將 Hash運(yùn)算結(jié)果的 Hash 值和所對應(yīng)的行指針信息存放于一個 Hash 表中，由于不同索引鍵存在相同 Hash 值，

所以即使取滿足某個 Hash 鍵值的數(shù)據(jù)的記錄條數(shù)，也無法從 Hash 索引中直接完成查詢，還是要通過訪問表中的實際數(shù)據(jù)進(jìn)行相應(yīng)的比較，并得到相應(yīng)的結(jié)果。

5.Hash 索引遇到大量Hash值相等的情況后性能并不一定就會比B-Tree索引高。

對于選擇性比較低的索引鍵，如果創(chuàng)建 Hash 索引，那么將會存在大量記錄指針信息存于同一個 Hash 值相關(guān)聯(lián)。這樣要定位某一條記錄時就會非常麻煩，會浪費(fèi)多次表數(shù)據(jù)的訪問，而造成整體性能低下

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

3. B+樹索引和哈希索引的明顯區(qū)別就是：

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

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

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

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

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

4. 總結(jié)一下：

在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é)

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

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