MySQL數據庫索引選擇使用B+樹(shù)的原因是什么

這篇文章主要介紹數據庫索引選擇使用B+樹(shù)的原因是什么，文中介紹的非常詳細，具有一定的參考價(jià)值，感興趣的小伙伴們一定要看完！

一、二叉查找樹(shù)

（1）二叉樹(shù)簡(jiǎn)介：

二叉查找樹(shù)也稱(chēng)為有序二叉查找樹(shù)，滿(mǎn)足二叉查找樹(shù)的一般性質(zhì)，是指一棵空樹(shù)具有如下性質(zhì)：

1、任意節點(diǎn)左子樹(shù)不為空,則左子樹(shù)的值均小于根節點(diǎn)的值；

2、任意節點(diǎn)右子樹(shù)不為空,則右子樹(shù)的值均大于于根節點(diǎn)的值；

3、任意節點(diǎn)的左右子樹(shù)也分別是二叉查找樹(shù)；

4、沒(méi)有鍵值相等的節點(diǎn)；

上圖為一個(gè)普通的二叉查找樹(shù)，按照中序遍歷的方式可以從小到大的順序排序輸出：2、3、5、6、7、8。

對上述二叉樹(shù)進(jìn)行查找，如查鍵值為5的記錄，先找到根，其鍵值是6，6大于5，因此查找6的左子樹(shù)，找到3；而5大于3，再找其右子樹(shù)；一共找了3次。如果按2、3、5、6、7、8的順序來(lái)找同樣需求3次。用同樣的方法在查找鍵值為8的這個(gè)記錄，這次用了3次查找，而順序查找需要6次。計算平均查找次數得：順序查找的平均查找次數為（1+2+3+4+5+6）/ 6 = 3.3次，二叉查找樹(shù)的平均查找次數為（3+3+3+2+2+1）/6=2.3次。二叉查找樹(shù)的平均查找速度比順序查找來(lái)得更快。

（2）局限性及應用

一個(gè)二叉查找樹(shù)是由n個(gè)節點(diǎn)隨機構成，所以，對于某些情況，二叉查找樹(shù)會(huì )退化成一個(gè)有n個(gè)節點(diǎn)的線(xiàn)性鏈。如下圖：

大家看上圖，如果我們的根節點(diǎn)選擇是最小或者最大的數，那么二叉查找樹(shù)就完全退化成了線(xiàn)性結構。上圖中的平均查找次數為（1+2+3+4+5+5）/6=3.16次，和順序查找差不多。顯然這個(gè)二叉樹(shù)的查詢(xún)效率就很低，因此若想最大性能的構造一個(gè)二叉查找樹(shù)，需要這個(gè)二叉樹(shù)是平衡的（這里的平衡從一個(gè)顯著(zhù)的特點(diǎn)可以看出這一棵樹(shù)的高度比上一個(gè)輸的高度要大，在相同節點(diǎn)的情況下也就是不平衡），從而引出了一個(gè)新的定義-平衡二叉樹(shù)AVL。

二、AVL樹(shù)

（1）簡(jiǎn)介

AVL樹(shù)是帶有平衡條件的二叉查找樹(shù)，一般是用平衡因子差值判斷是否平衡并通過(guò)旋轉來(lái)實(shí)現平衡，左右子樹(shù)樹(shù)高不超過(guò)1，和紅黑樹(shù)相比，它是嚴格的平衡二叉樹(shù)，平衡條件必須滿(mǎn)足（所有節點(diǎn)的左右子樹(shù)高度差不超過(guò)1）。不管我們是執行插入還是刪除操作，只要不滿(mǎn)足上面的條件，就要通過(guò)旋轉來(lái)保持平衡，而旋轉是非常耗時(shí)的，由此我們可以知道AVL樹(shù)適合用于插入刪除次數比較少，但查找多的情況。

從上面是一個(gè)普通的平衡二叉樹(shù)，這張圖我們可以看出，任意節點(diǎn)的左右子樹(shù)的平衡因子差值都不會(huì )大于1。

（2）局限性

由于維護這種高度平衡所付出的代價(jià)比從中獲得的效率收益還大，故而實(shí)際的應用不多，更多的地方是用追求局部而不是非常嚴格整體平衡的紅黑樹(shù)。當然，如果應用場(chǎng)景中對插入刪除不頻繁，只是對查找要求較高，那么AVL還是較優(yōu)于紅黑樹(shù)。

（3）應用

1、Windows NT內核中廣泛存在；

三、紅黑樹(shù)

（1）簡(jiǎn)介

一種二叉查找樹(shù)，但在每個(gè)節點(diǎn)增加一個(gè)存儲位表示節點(diǎn)的顏色，可以是red或black。通過(guò)對任何一條從根到葉子的路徑上各個(gè)節點(diǎn)著(zhù)色的方式的限制，紅黑樹(shù)確保沒(méi)有一條路徑會(huì )比其它路徑長(cháng)出兩倍。它是一種弱平衡二叉樹(shù)(由于是若平衡，可以推出，相同的節點(diǎn)情況下，AVL樹(shù)的高度低于紅黑樹(shù))，相對于要求嚴格的AVL樹(shù)來(lái)說(shuō)，它的旋轉次數變少，所以對于搜索、插入、刪除操作多的情況下，我們就用紅黑樹(shù)。

（2）性質(zhì)

1、每個(gè)節點(diǎn)非紅即黑；

 2、根節點(diǎn)是黑的；

3、每個(gè)葉節點(diǎn)(葉節點(diǎn)即樹(shù)尾端NULL指針或NULL節點(diǎn))都是黑的；

4、如果一個(gè)節點(diǎn)是紅的,那么它的兩兒子都是黑的；

5、對于任意節點(diǎn)而言，其到葉子點(diǎn)樹(shù)NULL指針的每條路徑都包含相同數目的黑節點(diǎn)；

6、每條路徑都包含相同的黑節點(diǎn)；

（3）應用

1、廣泛用于C++的STL中，Map和Set都是用紅黑樹(shù)實(shí)現的；

2、著(zhù)名的Linux進(jìn)程調度Completely Fair Scheduler，用紅黑樹(shù)管理進(jìn)程控制塊，進(jìn)程的虛擬內存區域都存儲在一顆紅黑樹(shù)上，每個(gè)虛擬地址區域都對應紅黑樹(shù)的一個(gè)節點(diǎn)，左指針指向相鄰的地址虛擬存儲區域，右指針指向相鄰的高地址虛擬地址空間；

3、IO多路復用epoll的實(shí)現采用紅黑樹(shù)組織管理sockfd，以支持快速的增刪改查；

4、Nginx中用紅黑樹(shù)管理timer，因為紅黑樹(shù)是有序的，可以很快的得到距離當前最小的定時(shí)器；

5、Java中TreeMap的實(shí)現；

四、B/B+樹(shù)

說(shuō)了上述的三種樹(shù)：二叉查找樹(shù)、AVL和紅黑樹(shù)，似乎我們還沒(méi)有摸到MySQL為什么要使用B+樹(shù)作為索引的實(shí)現，不要急，接下來(lái)我們就先探討一下什么是B樹(shù)。

（1）簡(jiǎn)介

我們在MySQL中的數據一般是放在磁盤(pán)中的，讀取數據的時(shí)候肯定會(huì )有訪(fǎng)問(wèn)磁盤(pán)的操作，磁盤(pán)中有兩個(gè)機械運動(dòng)的部分，分別是盤(pán)片旋轉和磁臂移動(dòng)。盤(pán)片旋轉就是我們市面上所提到的多少轉每分鐘，而磁盤(pán)移動(dòng)則是在盤(pán)片旋轉到指定位置以后，移動(dòng)磁臂后開(kāi)始進(jìn)行數據的讀寫(xiě)。那么這就存在一個(gè)定位到磁盤(pán)中的塊的過(guò)程，而定位是磁盤(pán)的存取中花費時(shí)間比較大的一塊，畢竟機械運動(dòng)花費的時(shí)候要遠遠大于電子運動(dòng)的時(shí)間。當大規模數據存儲到磁盤(pán)中的時(shí)候，顯然定位是一個(gè)非?；ㄙM時(shí)間的過(guò)程，但是我們可以通過(guò)B樹(shù)進(jìn)行優(yōu)化，提高磁盤(pán)讀取時(shí)定位的效率。

為什么B類(lèi)樹(shù)可以進(jìn)行優(yōu)化呢？我們可以根據B類(lèi)樹(shù)的特點(diǎn)，構造一個(gè)多階的B類(lèi)樹(shù)，然后在盡量多的在結點(diǎn)上存儲相關(guān)的信息，保證層數盡量的少，以便后面我們可以更快的找到信息，磁盤(pán)的I/O操作也少一些，而且B類(lèi)樹(shù)是平衡樹(shù)，每個(gè)結點(diǎn)到葉子結點(diǎn)的高度都是相同，這也保證了每個(gè)查詢(xún)是穩定的。

總的來(lái)說(shuō)，B/B+樹(shù)是為了磁盤(pán)或其它存儲設備而設計的一種平衡多路查找樹(shù)(相對于二叉，B樹(shù)每個(gè)內節點(diǎn)有多個(gè)分支)，與紅黑樹(shù)相比，在相同的的節點(diǎn)的情況下，一顆B/B+樹(shù)的高度遠遠小于紅黑樹(shù)的高度(在下面B/B+樹(shù)的性能分析中會(huì )提到)。B/B+樹(shù)上操作的時(shí)間通常由存取磁盤(pán)的時(shí)間和CPU計算時(shí)間這兩部分構成，而CPU的速度非?？?，所以B樹(shù)的操作效率取決于訪(fǎng)問(wèn)磁盤(pán)的次數，關(guān)鍵字總數相同的情況下B樹(shù)的高度越小，磁盤(pán)I/O所花的時(shí)間越少。

注意B-樹(shù)就是B樹(shù)，-只是一個(gè)符號。

（2）B樹(shù)的性質(zhì)

1、定義任意非葉子結點(diǎn)最多只有M個(gè)兒子，且M>2；

2、根結點(diǎn)的兒子數為[2, M]；

3、除根結點(diǎn)以外的非葉子結點(diǎn)的兒子數為[M/2, M]；

4、每個(gè)結點(diǎn)存放至少M/2-1（取上整）和至多M-1個(gè)關(guān)鍵字；（至少2個(gè)關(guān)鍵字）

5、非葉子結點(diǎn)的關(guān)鍵字個(gè)數=指向兒子的指針個(gè)數-1；

6、非葉子結點(diǎn)的關(guān)鍵字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；

7、非葉子結點(diǎn)的指針：P[1], P[2], …, P[M]；其中P[1]指向關(guān)鍵字小于K[1]的子樹(shù)，P[M]指向關(guān)鍵字大于K[M-1]的子樹(shù)，其它P[i]指向關(guān)鍵字屬于(K[i-1], K[i])的子樹(shù)；

8、所有葉子結點(diǎn)位于同一層；

這里只是一個(gè)簡(jiǎn)單的B樹(shù)，在實(shí)際中B樹(shù)節點(diǎn)中關(guān)鍵字很多的，上面的圖中比如35節點(diǎn)，35代表一個(gè)key(索引)，而小黑塊代表的是這個(gè)key所指向的內容在內存中實(shí)際的存儲位置，是一個(gè)指針。

五、B+樹(shù)

（1）簡(jiǎn)介

B+樹(shù)是應文件系統所需而產(chǎn)生的一種B樹(shù)的變形樹(shù)（文件的目錄一級一級索引，只有最底層的葉子節點(diǎn)（文件）保存數據）非葉子節點(diǎn)只保存索引，不保存實(shí)際的數據，數據都保存在葉子節點(diǎn)中，這不就是文件系統文件的查找嗎?

我們就舉個(gè)文件查找的例子：有3個(gè)文件夾a、b、c， a包含b，b包含c，一個(gè)文件yang.c，a、b、c就是索引（存儲在非葉子節點(diǎn)）， a、b、c只是要找到的yang.c的key，而實(shí)際的數據yang.c存儲在葉子節點(diǎn)上。

所有的非葉子節點(diǎn)都可以看成索引部分！

（2）B+樹(shù)的性質(zhì)(下面提到的都是和B樹(shù)不相同的性質(zhì))

1、非葉子節點(diǎn)的子樹(shù)指針與關(guān)鍵字個(gè)數相同；

2、非葉子節點(diǎn)的子樹(shù)指針p[i],指向關(guān)鍵字值屬于[k[i],k[i+1]]的子樹(shù).(B樹(shù)是開(kāi)區間,也就是說(shuō)B樹(shù)不允許關(guān)鍵字重復,B+樹(shù)允許重復)；

3、為所有葉子節點(diǎn)增加一個(gè)鏈指針；

4、所有關(guān)鍵字都在葉子節點(diǎn)出現(稠密索引). (且鏈表中的關(guān)鍵字恰好是有序的)；

5、非葉子節點(diǎn)相當于是葉子節點(diǎn)的索引(稀疏索引),葉子節點(diǎn)相當于是存儲(關(guān)鍵字)數據的數據層；

6、更適合于文件系統；

非葉子節點(diǎn)（比如5，28，65）只是一個(gè)key（索引），實(shí)際的數據存在葉子節點(diǎn)上（5，8，9）才是真正的數據或指向真實(shí)數據的指針。

（3）應用　　

1、B和B+樹(shù)主要用在文件系統以及數據庫做索引，比如MySQL；

六、B/B+樹(shù)性能分析

n個(gè)節點(diǎn)的平衡二叉樹(shù)的高度為H(即logn)，而n個(gè)節點(diǎn)的B/B+樹(shù)的高度為logt((n+1)/2)+1；

若要作為內存中的查找表，B樹(shù)卻不一定比平衡二叉樹(shù)好，尤其當m較大時(shí)更是如此。因為查找操作CPU的時(shí)間在B-樹(shù)上是O(mlogtn)=O(lgn(m/lgt))，而m/lgt>1；所以m較大時(shí)O(mlogtn)比平衡二叉樹(shù)的操作時(shí)間大得多。因此在內存中使用B樹(shù)必須取較小的m。（通常取最小值m=3，此時(shí)B-樹(shù)中每個(gè)內部結點(diǎn)可以有2或3個(gè)孩子，這種3階的B-樹(shù)稱(chēng)為2-3樹(shù)）。

七、為什么說(shuō)B+樹(shù)比B樹(shù)更適合數據庫索引？

1、 B+樹(shù)的磁盤(pán)讀寫(xiě)代價(jià)更低：B+樹(shù)的內部節點(diǎn)并沒(méi)有指向關(guān)鍵字具體信息的指針，因此其內部節點(diǎn)相對B樹(shù)更小，如果把所有同一內部節點(diǎn)的關(guān)鍵字存放在同一盤(pán)塊中，那么盤(pán)塊所能容納的關(guān)鍵字數量也越多，一次性讀入內存的需要查找的關(guān)鍵字也就越多，相對IO讀寫(xiě)次數就降低了。

2、B+樹(shù)的查詢(xún)效率更加穩定：由于非終結點(diǎn)并不是最終指向文件內容的結點(diǎn)，而只是葉子結點(diǎn)中關(guān)鍵字的索引。所以任何關(guān)鍵字的查找必須走一條從根結點(diǎn)到葉子結點(diǎn)的路。所有關(guān)鍵字查詢(xún)的路徑長(cháng)度相同，導致每一個(gè)數據的查詢(xún)效率相當。

3、由于B+樹(shù)的數據都存儲在葉子結點(diǎn)中，分支結點(diǎn)均為索引，方便掃庫，只需要掃一遍葉子結點(diǎn)即可，但是B樹(shù)因為其分支結點(diǎn)同樣存儲著(zhù)數據，我們要找到具體的數據，需要進(jìn)行一次中序遍歷按序來(lái)掃，所以B+樹(shù)更加適合在區間查詢(xún)的情況，所以通常B+樹(shù)用于數據庫索引。

PS：我在知乎上看到有人是這樣說(shuō)的,我感覺(jué)說(shuō)的也挺有道理的：

他們認為數據庫索引采用B+樹(shù)的主要原因是：B樹(shù)在提高了IO性能的同時(shí)并沒(méi)有解決元素遍歷的我效率低下的問(wèn)題，正是為了解決這個(gè)問(wèn)題，B+樹(shù)應用而生。B+樹(shù)只需要去遍歷葉子節點(diǎn)就可以實(shí)現整棵樹(shù)的遍歷。而且在數據庫中基于范圍的查詢(xún)是非常頻繁的，而B(niǎo)樹(shù)不支持這樣的操作或者說(shuō)效率太低。