MySQL中B-tree索引和Hash索引区别
在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)容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: python logging日志模块的使
- 下一篇: 第44讲:scrapy中间键Middle