索引介紹

索引是一種特殊的數(shù)據(jù)庫(kù)結(jié)構(gòu)，被設(shè)計(jì)用來(lái)快速查詢數(shù)據(jù)庫(kù)表中的特定記錄。索引有多種類型，就像字典有拼音查找和偏旁查找一樣都是為了提高檢索效率。MySQL中最常見(jiàn)的索引類型有B+樹(shù)索引 和 哈希索引，下面來(lái)簡(jiǎn)單介紹一下這兩種索引類型有哪些差別和優(yōu)劣。

B+樹(shù)索引

B+樹(shù)索引是一種多路徑的平衡搜索樹(shù)，具有如下特點(diǎn)：

• 1.非葉子節(jié)點(diǎn)不保存數(shù)據(jù)，只保存索引值

• 2.葉子節(jié)點(diǎn)保存所有的索引值和數(shù)據(jù)

• 3.同級(jí)節(jié)點(diǎn)通過(guò)指針自小而大順序鏈接

• 4.節(jié)點(diǎn)內(nèi)的數(shù)據(jù)也是自小而大順序存放

• 5.葉子節(jié)點(diǎn)擁有父節(jié)點(diǎn)的所有信息

結(jié)構(gòu)如下圖：

優(yōu)點(diǎn)

• 由于數(shù)據(jù)順序存放，所以無(wú)論是區(qū)間還是順序掃描都更快。

• 非葉子節(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù)，因此幾乎都能放在內(nèi)存中，搜索效率更高

• 單節(jié)點(diǎn)中可存儲(chǔ)的數(shù)據(jù)更多，平均掃描I/O請(qǐng)求樹(shù)更少

• 平均查詢效率穩(wěn)定（每次查詢都從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)，查詢路徑長(zhǎng)度相同）

缺點(diǎn)

• 新增數(shù)據(jù)不是按順序遞增時(shí)，索引樹(shù)需要重新排列，容易造成碎片和頁(yè)分裂情況。

哈希索引

哈希索引采用一定的哈希算法，把鍵值換算成新的哈希值，檢索時(shí)不需要類似B+樹(shù)那樣從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)逐級(jí)查找，只需一次哈希算法即可立刻定位到相應(yīng)的位置，速度非常快，具有如下特點(diǎn)：

• 1.哈希索引建立在哈希表的基礎(chǔ)上

• 2.對(duì)于每個(gè)值，需要先計(jì)算出對(duì)應(yīng)的哈希碼（Hash Code），不同值的哈希碼唯一

• 3.把哈希碼保存在哈希表中，同時(shí)哈希表也保存指向?qū)?yīng)每行記錄的指針

結(jié)構(gòu)如下圖：

優(yōu)點(diǎn)

• 大量唯一等值查詢時(shí)，哈希索引效率通常更高。

缺點(diǎn)

• 哈希索引對(duì)于范圍查詢和模糊匹配查詢顯得無(wú)能為力。

• 哈希索引不支持排序操作，對(duì)于多列聯(lián)合索引的最左匹配規(guī)則也不支持。

• 哈希索引不支持前綴索引，因?yàn)楣Ｋ饕冀K是使用索引列的全部?jī)?nèi)容來(lái)計(jì)算哈希值。

• 如果存在哈希沖突的情況，也就是不同的索引列有著相同的哈希值，這時(shí)候需要遍歷鏈表中所有的行指針進(jìn)行逐行比對(duì)，直到找到所有滿足條件的行，效率較低。

補(bǔ)充：二者區(qū)別

備注：先說(shuō)下，在MySQL文檔里，實(shí)際上是把B+樹(shù)索引寫(xiě)成了BTREE，例如像下面這樣的寫(xiě)法：

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個(gè)字符長(zhǎng)度的部分索引
)engine=InnoDB;

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

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

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

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

• 從示意圖中也能看到，如果是范圍查詢檢索，這時(shí)候哈希索引就毫無(wú)用武之地了，因?yàn)樵仁怯行虻逆I值，經(jīng)過(guò)哈希算法后，有可能變成不連續(xù)的了，就沒(méi)辦法再利用索引完成范圍查詢檢索；

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

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

• B+樹(shù)索引的關(guān)鍵字檢索效率比較平均，不像B樹(shù)那樣波動(dòng)幅度大，在有大量重復(fù)鍵值情況下，哈希索引的效率也是極低的，因?yàn)榇嬖谒^的哈希碰撞問(wèn)題。

總結(jié) 

到此這篇關(guān)于MySQL B+樹(shù)索引與哈希索引的文章就介紹到這了,更多相關(guān)MySQL B+樹(shù)索引與哈希索引內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論