前言

B+樹(shù)是目前最常用的一種索引數(shù)據(jù)結(jié)構(gòu),通常用于數(shù)據(jù)庫(kù)和操作系統(tǒng)的文件系統(tǒng)中,本文就網(wǎng)上的知識(shí)點(diǎn)與個(gè)人理解結(jié)合分享,如有錯(cuò)誤,歡迎探討及指正.

定義

B+樹(shù)是B樹(shù)的一種變形形式，B+樹(shù)上的葉子結(jié)點(diǎn)存儲(chǔ)關(guān)鍵字以及相應(yīng)記錄的地址，葉子結(jié)點(diǎn)以上各層作為索引使用。一棵m階的B+樹(shù)定義如下(==注意: B+樹(shù)的階數(shù)m表示一個(gè)節(jié)點(diǎn)最多能有m個(gè)子節(jié)點(diǎn),也就是每個(gè)節(jié)點(diǎn)上最多的鍵值個(gè)數(shù).==):
1.每個(gè)結(jié)點(diǎn)至多有m個(gè)子女;
2.除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)至少有[m/2]個(gè)子女，根結(jié)點(diǎn)至少有兩個(gè)子女;
3.有k個(gè)子女的結(jié)點(diǎn)必有k個(gè)關(guān)鍵字。

B+樹(shù)的查找與B樹(shù)不同，當(dāng)索引部分某個(gè)結(jié)點(diǎn)的關(guān)鍵字與所查的關(guān)鍵字相等時(shí)，并不停止查找，應(yīng)繼續(xù)沿著這個(gè)關(guān)鍵字左邊的指針向下，一直查到該關(guān)鍵字所在的葉子結(jié)點(diǎn)為止。

圖文理解

下面我們通過(guò)圖文詳解來(lái)深入理解B+樹(shù)

不同階數(shù)的B+樹(shù)對(duì)比

我們將數(shù)組[1,2,3,4...20]分別插入3階、4階、5階、6階B+數(shù),最終存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)如下圖:

• 3階B+樹(shù) :

• 4階B+數(shù):

• 5階B+數(shù):

• 6階B+數(shù):

通過(guò)上面對(duì)比,我們不難發(fā)現(xiàn)以下特征:

• 所有節(jié)點(diǎn)均有序排列;
• 樹(shù)節(jié)點(diǎn)總是樹(shù)高平衡;
• m階的B+樹(shù)除了根節(jié)點(diǎn)之外的每個(gè)節(jié)點(diǎn)都包含最少 m/2個(gè)元素,但最多包含 m-1 個(gè)元素(文末提供在線測(cè)試地址,可以自行刪減元素,觀察葉子結(jié)點(diǎn)的變化);
• 對(duì)于任意的節(jié)點(diǎn)有最多 m 個(gè)子指針;
• 對(duì)于所有內(nèi)部節(jié)點(diǎn),子指針的數(shù)目總是比元素的數(shù)目多一個(gè);
• 階數(shù)越大,數(shù)的高度越小.
• 所有數(shù)據(jù)存儲(chǔ)在葉子結(jié)點(diǎn)上,非葉子節(jié)點(diǎn)不存儲(chǔ)行數(shù)據(jù),是為了能存儲(chǔ)更多索引鍵,從而降低B+樹(shù)的高度，進(jìn)而減少I(mǎi)O次數(shù).

B+樹(shù)insert/delete操作后數(shù)據(jù)結(jié)構(gòu)的變化

本次我們演示4階B+樹(shù)操作的變化過(guò)程

• 第一步:我們先插入數(shù)字1、2、3

• 
  第二步:插入數(shù)字4,由于每個(gè)節(jié)點(diǎn)最多只能有m-1個(gè)元素,即超過(guò)3個(gè)后需要進(jìn)行拆分頁(yè),而目前只有一個(gè)根節(jié)點(diǎn),所以旋轉(zhuǎn)后樹(shù)的深度+1.

• 
  第三步:分別插入數(shù)字5、6,根據(jù)樹(shù)結(jié)構(gòu)的特性拆分頁(yè),如下圖

• 第四步:分別插入數(shù)字7、8、9

• 插入10的時(shí)候,觸發(fā)每個(gè)節(jié)點(diǎn)最多只能有m-1個(gè)元素的特性,同時(shí)觸發(fā)了[任意的節(jié)點(diǎn)有最多 m 個(gè)子指針]的特性,所以繼續(xù)旋轉(zhuǎn)后樹(shù)的深度+1.

• 
  第五步:前面四步演示了樹(shù)的旋轉(zhuǎn)以及拆分頁(yè),接下來(lái)我們看下刪除元素會(huì)是什么樣的效果,先刪除元素10看下:

在第四步最后我們?cè)黾右粋€(gè)元素10,觸發(fā)了B+樹(shù)的特性調(diào)整了樹(shù)的高度,現(xiàn)在我們刪除元素10,從上圖可以看出樹(shù)的高度沒(méi)有變化,這點(diǎn)跟平衡樹(shù)不一樣,我們繼續(xù)刪元素.

刪除元素7之后,層級(jí)沒(méi)有變化,但是第二級(jí)的右子節(jié)點(diǎn)元素值發(fā)生了旋轉(zhuǎn),由7變成了6,繼續(xù)刪除元素6:

我們發(fā)現(xiàn)刪除元素6后,樹(shù)的層級(jí)發(fā)生了變化,這是因?yàn)橛|發(fā)了[對(duì)于所有內(nèi)部節(jié)點(diǎn),子指針的數(shù)目總是比元素的數(shù)目多一個(gè)]這一特性,然后根據(jù)最優(yōu)算法降低了樹(shù)的高度,同時(shí)我們發(fā)現(xiàn),此時(shí)的5個(gè)元素排列并沒(méi)有恢復(fù)到我們之前從元素[1-5]插入后的結(jié)構(gòu),這點(diǎn)非常妙,不管接下來(lái)是新增、刪除、查找你會(huì)發(fā)現(xiàn)效率都是最優(yōu)的.

B+樹(shù)的查找

我們還是以4階樹(shù)10個(gè)元素為例,查找元素6

從上可以看出查找路線與二叉樹(shù)的查找規(guī)則一致,繼續(xù)查找元素5

結(jié)合這兩次查找,可以看出都消耗了3次IO找到數(shù)據(jù),這個(gè)次數(shù)剛好等于數(shù)的高度,數(shù)據(jù)量少時(shí)看不出這個(gè)效率,假設(shè)是100階的樹(shù),存儲(chǔ)了400w+數(shù)據(jù),實(shí)際也是3次IO就可以找到想要的數(shù)據(jù),這個(gè)時(shí)候B+樹(shù)的優(yōu)勢(shì)就體現(xiàn)出來(lái)了.

至此,相信你對(duì)B+樹(shù)又有了更直觀的認(rèn)識(shí),接下來(lái)我們?cè)倭牧膍ysql應(yīng)用的B+樹(shù)索引.

mysql的B+樹(shù)索引

mysql的B+樹(shù)索引有多少階?

對(duì)于這個(gè)問(wèn)題,我們需要先了解下磁盤(pán)相關(guān)知識(shí).

• 磁盤(pán)的最小存儲(chǔ)單位是扇區(qū)(512字節(jié))
• 磁盤(pán)的讀取是以塊為基本單位,一塊大小為8個(gè)扇區(qū),即4kb
• B+樹(shù)的每一個(gè)節(jié)點(diǎn)占用的空間就是一個(gè)塊大小

由于B+樹(shù)節(jié)點(diǎn)中只存儲(chǔ)元素和指針.如果有n個(gè)元素，那么就有n+1個(gè)指針,假設(shè)現(xiàn)在索引存儲(chǔ)int類(lèi)型的值,一個(gè)int(32位)占用4個(gè)字節(jié),一個(gè)指針占用8個(gè)字節(jié),那么一個(gè)塊最多能存4096/(4n+8(n+1))即340個(gè)元素,那么索引即為341階(m階數(shù)最多包含m-1個(gè)元素).

mysql的B+樹(shù)索引能存多少數(shù)據(jù)?

以innodb引擎的索引數(shù)據(jù)結(jié)構(gòu)為例,它的存儲(chǔ)單元為一頁(yè),每頁(yè)大小默認(rèn)為16kb,該值可以通過(guò)參數(shù)調(diào)整,如下圖.

• 
  假設(shè)每個(gè)節(jié)點(diǎn)中索引元素占8個(gè)字節(jié),指針占用6個(gè)字節(jié),那么每頁(yè)可存(16*1024)/(8+6)=1170個(gè)索引元素
• 假設(shè)B+樹(shù)的高度為3,一條數(shù)據(jù)大小為1k,那么: 第一層可以存1170個(gè)元素; 第二層可以存11701170=1368900個(gè)元素; 第三層屬于葉子結(jié)點(diǎn),可以存的數(shù)據(jù)條數(shù)為頁(yè)大小16k/每條數(shù)據(jù)大小1k,即16條,那么總共可以存儲(chǔ)的數(shù)據(jù)條數(shù)即為161368900=21902400

總結(jié):mysql 單表使用innodb引擎(表數(shù)據(jù)文件本身就是一個(gè)B+樹(shù)組織的索結(jié)構(gòu)文件),默認(rèn)至少可以存2000w數(shù)據(jù)(實(shí)際每個(gè)節(jié)點(diǎn)不只存儲(chǔ)了元素及指針),并且查找數(shù)據(jù),最多3次io即可.

資料參考

• 非常經(jīng)典的數(shù)據(jù)結(jié)構(gòu)可視化工具 https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html

• 百度百科 https://baike.baidu.com/item/B+%E6%A0%91/7845683#reference-[3]-1168762-wrap

歡迎關(guān)注個(gè)人訂閱號(hào):Java技術(shù)寶典 ,及時(shí)獲取最新分享.