MySQL為什么使用B+樹

Mysql為什么使用B+樹

解析為什么Mysql要使用B+樹的數(shù)據(jù)結(jié)構(gòu)

確切的說是MySQL使用了InnoDB引擎，而InnoDB使用的B+樹結(jié)構(gòu)

1.各種數(shù)據(jù)結(jié)構(gòu)的對(duì)比

1.1 哈希表

哈希表是一種以鍵-值（key-value）存儲(chǔ)數(shù)據(jù)的結(jié)構(gòu)，只要輸入待查找的值即key，就可以找到其對(duì)應(yīng)的值即Value，時(shí)間復(fù)雜度為O(1)，但是容易發(fā)生哈希沖突，當(dāng)發(fā)生沖突時(shí)，常用開放地址法、拉鏈法、再散列法解決

因?yàn)閂alue不是有序存儲(chǔ)的，所以哈希索引做區(qū)間查詢的速度是很慢的，范圍查找時(shí)只能通過掃描全表的方式，所以哈希表這種結(jié)構(gòu)適用于只有等值查詢的場(chǎng)景，而不適用于范圍查詢

1.2 有序數(shù)組

有序數(shù)組在等值查詢和范圍查詢場(chǎng)景中的性能都非常優(yōu)秀，等值查詢的時(shí)候可以用二分查找，時(shí)間復(fù)雜度為O(log(N))；范圍查詢時(shí)可以先用二分查找找到第一個(gè)值，然后向右遍歷。

如果僅僅看查詢效率，有序數(shù)組是最好的數(shù)據(jù)結(jié)構(gòu)，但是要更新數(shù)據(jù)時(shí)就必須挪動(dòng)后面所有的數(shù)據(jù)，成本太高。所以有序數(shù)組索引只適用于查詢的情況

1.3 紅黑樹

紅黑樹是一種平衡二叉查找樹的變體，它的左右子樹高差有可能大于 1，所以紅黑樹不是嚴(yán)格意義上的平衡二叉樹（AVL），但其平衡的代價(jià)較低， 其平均統(tǒng)計(jì)性能要強(qiáng)于 AVL 。

以升序插入構(gòu)建紅黑樹

以降序插入構(gòu)建紅黑樹

隨機(jī)插入構(gòu)建紅黑樹

因?yàn)榧t黑樹中每個(gè)結(jié)點(diǎn)都會(huì)存放一個(gè)數(shù)據(jù)，而不僅僅只起索引作用，除此之外紅黑樹一個(gè)結(jié)點(diǎn)只存放一個(gè)key，結(jié)點(diǎn)利用率低，而B/B+樹一個(gè)結(jié)點(diǎn)可以存放多個(gè)關(guān)鍵字，在關(guān)鍵字總數(shù)相同的情況下，紅黑樹的高度總是大于B/B+樹，在大規(guī)模數(shù)據(jù)存儲(chǔ)的時(shí)候，紅黑樹會(huì)出現(xiàn)樹的深度過大而造成磁盤IO讀寫過于頻繁，進(jìn)而導(dǎo)致效率低下。

1.4 B樹（B-樹）

一顆m階的B樹的定義如下：

每個(gè)節(jié)點(diǎn)最多有m-1個(gè)關(guān)鍵字

根節(jié)點(diǎn)最少可以只有一個(gè)關(guān)鍵字

非根節(jié)點(diǎn)至少有?m/2?-1個(gè)關(guān)鍵字

每個(gè)節(jié)點(diǎn)的關(guān)鍵字都按照從小到大的順序排列，每個(gè)關(guān)鍵字的左子樹中的所有關(guān)鍵字都小于它，而右子樹中的所有關(guān)鍵字都大于它

所有葉子節(jié)點(diǎn)都位于同一層，或者說根節(jié)點(diǎn)到每個(gè)葉子節(jié)點(diǎn)的路徑長(zhǎng)度都相同

將一個(gè)key和其對(duì)應(yīng)的data稱為一個(gè)記錄，MySQL數(shù)據(jù)庫中如果以B樹作為索引結(jié)構(gòu)，此時(shí)上圖的黃色結(jié)點(diǎn)key表示鍵，而綠色結(jié)點(diǎn)data表示這個(gè)鍵對(duì)應(yīng)的條目在磁盤上的邏輯地址

1.5 B+樹

B+樹的特性：

B+樹包含2種類型的節(jié)點(diǎn)：內(nèi)部節(jié)點(diǎn)（也稱索引節(jié)點(diǎn)）和葉子節(jié)點(diǎn)。根節(jié)點(diǎn)本身即可以是內(nèi)部節(jié)點(diǎn)，也可以是葉子節(jié)點(diǎn)。根節(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)最少可以只有1個(gè)

B+樹與B樹最大的不同是內(nèi)部節(jié)點(diǎn)不保存數(shù)據(jù)，只用于索引，所有數(shù)據(jù)（或者說記錄）都保存在葉子節(jié)點(diǎn)中

m階B+樹表示了內(nèi)部節(jié)點(diǎn)最多有m-1個(gè)關(guān)鍵字（或者說內(nèi)部節(jié)點(diǎn)最多有m個(gè)子樹），階數(shù)m同時(shí)限制了葉子節(jié)點(diǎn)最多存儲(chǔ)m-1個(gè)記錄

內(nèi)部節(jié)點(diǎn)中的key都按照從小到大的順序排列，對(duì)于內(nèi)部節(jié)點(diǎn)中的一個(gè)key，左樹中的所有key都小于它，右子樹中的key都大于等于它。葉子節(jié)點(diǎn)中的記錄也按照key的大小排列

每個(gè)葉子節(jié)點(diǎn)都存有相鄰葉子節(jié)點(diǎn)的指針，葉子節(jié)點(diǎn)本身依關(guān)鍵字的大小自小而大順序鏈接

B+樹因?yàn)橹挥腥~子結(jié)點(diǎn)才保存數(shù)據(jù)，內(nèi)部節(jié)點(diǎn)只是作為索引，因此一個(gè)內(nèi)存頁可以存放更多的key，數(shù)據(jù)的存放更加緊密，具有更好的局部性，命中率更高，查詢速度更快；B+樹的相鄰葉子結(jié)點(diǎn)有指針相連，且自小而大順序鏈接，所以也適合做范圍查詢

1.6 總結(jié)

使用B+樹而不是其它數(shù)據(jù)結(jié)構(gòu)的原因：

哈希表只適合等值查詢，而不適合范圍查詢

有序數(shù)組挪動(dòng)數(shù)據(jù)的成本太高

紅黑樹結(jié)點(diǎn)利用率低，層數(shù)高，不適合做范圍查詢

B樹結(jié)點(diǎn)除了存放索引外還會(huì)存放數(shù)據(jù)，每個(gè)內(nèi)存頁的利用率不如B+樹，且B樹做范圍查詢時(shí)要進(jìn)行每一層的遞歸遍歷，效率不如B+樹。但B樹也有優(yōu)點(diǎn)，由于B樹的每一個(gè)節(jié)點(diǎn)都包含key和value，因此經(jīng)常訪問的元素可能離根節(jié)點(diǎn)更近，因此訪問也更迅速

B+樹因?yàn)橹挥腥~子結(jié)點(diǎn)才保存數(shù)據(jù)，內(nèi)部節(jié)點(diǎn)只是作為索引，所以相比于B樹一個(gè)內(nèi)存頁可以存放更多的key，數(shù)據(jù)的存放更加緊密，具有更好的局部性，命中率更高；同時(shí)B+樹的相鄰葉子結(jié)點(diǎn)有指針相連，且自小而大順序鏈接，所以也適合做范圍查詢，MySQL中范圍查詢是很頻繁的，而B樹不支持這樣的操作導(dǎo)致效率太低；還有，B+樹的所有value都在葉子結(jié)點(diǎn)，所以B+樹到葉子結(jié)點(diǎn)的索引長(zhǎng)度總是相等的，比B樹更穩(wěn)定

因?yàn)锽樹和B+樹一個(gè)結(jié)點(diǎn)可以存放多個(gè)key或value，相比普通的二叉樹整體的高度更低，可以減少磁盤IO的次數(shù)，而B+樹又比B樹的高度更低，所以最終選擇了B+樹

2.B+樹在MySQL中的應(yīng)用

2.1 聚簇索引

當(dāng)表有聚簇索引時(shí)，它的數(shù)據(jù)行實(shí)際上存放在索引的葉子頁中，“聚簇”即數(shù)據(jù)行相鄰的鍵值緊湊的存儲(chǔ)在一起。因?yàn)闊o法同時(shí)把數(shù)據(jù)行存放在兩個(gè)不同的地方，所以一個(gè)表只能有一個(gè)聚簇索引

從上面的圖可知采用了B+樹的結(jié)構(gòu)，因?yàn)榘褦?shù)據(jù)都保存在一起，這樣只需從磁盤讀少許的數(shù)據(jù)頁就能獲取大量的數(shù)據(jù)value，減少了磁盤IO。

與聚簇索引相對(duì)應(yīng)的是非聚簇索引，也叫做二級(jí)索引，二級(jí)索引訪問需要兩次索引查找。因?yàn)槎?jí)索引葉子結(jié)點(diǎn)保存不是行指針，而是行的主鍵值，找到主鍵值后還要根據(jù)主鍵值去聚簇索引中查找對(duì)應(yīng)的行

2.2 覆蓋索引

覆蓋索引只能通過B+樹來實(shí)現(xiàn)，因?yàn)楣Ｋ饕⑷乃饕榷疾淮鎯?chǔ)索引列的值。覆蓋索引指一個(gè)索引包含（覆蓋）了所有要查詢的字段的值

如上圖所示，如果執(zhí)行語句select * from T where k between 3 and 5，流程如下：

在k索引樹上找到k=3的記錄，取得ID=300

再到ID索引樹查到ID=300對(duì)應(yīng)的R3（第一次回表）

在k索引樹取下一個(gè)值k=5，取得ID=500

再回到ID索引樹查到ID=500對(duì)應(yīng)的R4（第二次回表）

在k索引樹取下一個(gè)值k=6，不滿足條件，循環(huán)結(jié)束。

可見，回表了兩次。而通過覆蓋索引可以避免回表過程

如果執(zhí)行select ID from Table where k between 3 and 5查詢語句，由于用到了覆蓋索引，這時(shí)只需要查ID的值，而ID的值已經(jīng)在k索引樹上了，因此可以直接提供查詢結(jié)果，不需要回表。也就是說，在這個(gè)查詢里面，索引k已經(jīng)“覆蓋了”我們的查詢需求，我們稱為覆蓋索引

2.3 自增主鍵

B+樹為了維護(hù)索引有序性，在插入新值的時(shí)候需要做必要的維護(hù)。根據(jù)B+樹的算法，為了保持B+樹的平衡，當(dāng)一個(gè)數(shù)據(jù)頁插滿后會(huì)申請(qǐng)一個(gè)新的數(shù)據(jù)頁，然后挪動(dòng)部分?jǐn)?shù)據(jù)過去，稱為頁分裂，這個(gè)過程會(huì)影響性能，而且整體空間利用率會(huì)降低50%；當(dāng)刪除部分頁數(shù)據(jù)后，頁的利用率會(huì)降低，會(huì)做頁合并操作，如果沒有自增主鍵，頻繁的頁分裂和合并會(huì)導(dǎo)致效率變低

如果表使用自增主鍵，那么每次插入新的記錄，記錄就會(huì)順序添加到當(dāng)前索引節(jié)點(diǎn)的后續(xù)位置，當(dāng)一頁寫滿，就會(huì)自動(dòng)開辟一個(gè)新的頁，不涉及到挪動(dòng)其他記錄，也不會(huì)觸發(fā)葉子節(jié)點(diǎn)的分裂。而若有業(yè)務(wù)邏輯的字段做主鍵，則往往不容易保證有序插入，這樣寫數(shù)據(jù)成本相對(duì)較高。所以自增主鍵總的來說就是可以提高查詢和增刪的性能。

同時(shí)，主鍵長(zhǎng)度越小，普通索引的葉子節(jié)點(diǎn)就越小，普通索引占用的空間也就越小，所以，從性能和存儲(chǔ)空間方面考量，自增主鍵往往是更合理的選擇

2.4 最左前綴原則

創(chuàng)建一個(gè)三列的聯(lián)合索引包含(col1, col2, col3)，索引會(huì)生效于(col1)，(col1, col2)以及(col1, col2, col3)

比如以下示例：

1. SELECT * FROM tbl_name WHERE col1=val1; 2. SELECT * FROM tbl_name WHERE col1=val1 AND col2=val2; 3. SELECT * FROM tbl_name WHERE col2=val2 AND col1=val1; 4. SELECT * FROM tbl_name WHERE col2=val2; 5. SELECT * FROM tbl_name WHERE col2=val2 AND col3=val3; 6. SELECT * FROM tbl_name WHERE col1=val1 AND col3=val3;

第一條和第二條和第三條查詢語句用到了索引，第二條和第三條效果是一樣的，即與where語句中字段出現(xiàn)的順序無關(guān)

第四條和第五條查詢雖然包含索引的列,，但是不會(huì)用索引去執(zhí)行查詢，因?yàn)?col2)和(col2, col3) 不是(col1, col2, col3)的最左前綴

第六條查詢只會(huì)執(zhí)行(col1)的索引查詢

若字段為字符串，則對(duì)于索引的第一個(gè)字段，用like時(shí)左邊必須是固定值，通配符只能出現(xiàn)在右邊，select * from AAA where a like '張%'會(huì)用到索引；而select * from AAA where a like '%三'不會(huì)用到索引。

從上圖可以看到最左前綴原則和B+樹的結(jié)合 ，先按名字搜索，然后在此基礎(chǔ)上按歲數(shù)搜索，在搜索名字的時(shí)候還可以采用給字符串添加搜索的方式，比如：where name like '張%'，會(huì)找到ID3的位置，然后再匹配名字的全稱，然后再匹配歲數(shù)。

MySQL 數(shù)據(jù)結(jié)構(gòu)

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實(shí)的內(nèi)容，請(qǐng)聯(lián)系我們jiasou666@gmail.com 處理，核實(shí)后本網(wǎng)站將在24小時(shí)內(nèi)刪除侵權(quán)內(nèi)容。

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實(shí)的內(nèi)容，請(qǐng)聯(lián)系我們jiasou666@gmail.com 處理，核實(shí)后本網(wǎng)站將在24小時(shí)內(nèi)刪除侵權(quán)內(nèi)容。