結(jié)點(diǎn)的分支數(shù)等于關(guān)鍵字?jǐn)?shù)+1舱痘，最大的分支數(shù)就是B-樹(shù)的階數(shù)举娩，因此m階的B-樹(shù)中結(jié)點(diǎn)最多有m個(gè)分支
B-Tree
摘抄自：http://www.reibang.com/p/7dedb7ebe033
B-樹(shù)中所有結(jié)點(diǎn)中孩子結(jié)點(diǎn)個(gè)數(shù)的最大值成為B-樹(shù)的階并级，通常用m表示，從查找效率考慮，一般要求m>=3翘贮。一棵m階B-樹(shù)或者是一棵空樹(shù)幻赚，或者是滿足以下條件的m叉樹(shù)禀忆。
1）每個(gè)結(jié)點(diǎn)最多有m個(gè)分支（子樹(shù)）；而最少分支數(shù)要看是否為根結(jié)點(diǎn)落恼，如果是根結(jié)點(diǎn)且不是葉子結(jié)點(diǎn)箩退，則至少要有兩個(gè)分支，非根非葉結(jié)點(diǎn)至少有ceil(m/2)個(gè)分支佳谦，這里ceil代表向上取整戴涝。
2）如果一個(gè)結(jié)點(diǎn)有n-1個(gè)關(guān)鍵字，那么該結(jié)點(diǎn)有n個(gè)分支钻蔑。這n-1個(gè)關(guān)鍵字按照遞增順序排列啥刻。
3）每個(gè)結(jié)點(diǎn)的結(jié)構(gòu)為：
| n | k1 | k2 | ... | kn |
|---|---|---|---|---|
| p0 | p1 | p2 | ... | pn |
其中，n為該結(jié)點(diǎn)中關(guān)鍵字的個(gè)數(shù)咪笑；ki為該結(jié)點(diǎn)的關(guān)鍵字且滿足ki<ki+1可帽；pi為該結(jié)點(diǎn)的孩子結(jié)點(diǎn)指針且滿足pi所指結(jié)點(diǎn)上的關(guān)鍵字大于ki且小于ki+1垮斯，p0所指結(jié)點(diǎn)上的關(guān)鍵字小于k1怎憋，pn所指結(jié)點(diǎn)上的關(guān)鍵字大于kn。
4）結(jié)點(diǎn)內(nèi)各關(guān)鍵字互不相等且按從小到大排列拗小。
5）葉子結(jié)點(diǎn)處于同一層扬虚；可以用空指針表示申窘，是查找失敗到達(dá)的位置。
注：平衡m叉查找樹(shù)是指每個(gè)關(guān)鍵字的左側(cè)子樹(shù)與右側(cè)子樹(shù)的高度差的絕對(duì)值不超過(guò)1的查找樹(shù)孔轴，其結(jié)點(diǎn)結(jié)構(gòu)與上面提到的B-樹(shù)結(jié)點(diǎn)結(jié)構(gòu)相同剃法，由此可見(jiàn)，B-樹(shù)是平衡m叉查找樹(shù)路鹰，但限制更強(qiáng)贷洲，要求所有葉結(jié)點(diǎn)都在同一層。
光看上面的解釋可能大家對(duì)B-樹(shù)理解的還不是那么透徹晋柱，下面我們用一個(gè)實(shí)例來(lái)進(jìn)行講解优构。
上面的圖片顯示了一棵B-樹(shù)，最底層的葉子結(jié)點(diǎn)沒(méi)有顯示雁竞。我們對(duì)上面提到的5條特點(diǎn)進(jìn)行逐條解釋：
1）結(jié)點(diǎn)的分支數(shù)等于關(guān)鍵字?jǐn)?shù)+1钦椭，最大的分支數(shù)就是B-樹(shù)的階數(shù)拧额，因此m階的B-樹(shù)中結(jié)點(diǎn)最多有m個(gè)分支，所以可以看到彪腔，上面的一棵樹(shù)是一個(gè)5-階B-樹(shù)侥锦。
2）因?yàn)樯厦媸且豢?階B-樹(shù)，所以非根非葉結(jié)點(diǎn)至少要有ceil(5/2)=3個(gè)分支德挣。根結(jié)點(diǎn)可以不滿足這個(gè)條件恭垦，圖中的根結(jié)點(diǎn)有兩個(gè)分支。
3）如果根結(jié)點(diǎn)中沒(méi)有關(guān)鍵字就沒(méi)有分支格嗅，此時(shí)B-樹(shù)是空樹(shù)番挺，如果根結(jié)點(diǎn)有關(guān)鍵字，則其分支數(shù)比大于或等于2屯掖，因?yàn)榉种?shù)等于關(guān)鍵字?jǐn)?shù)+1.
4）上圖中除根結(jié)點(diǎn)外玄柏，結(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù)至少為2，因?yàn)榉种?shù)至少為3贴铜，分支數(shù)比關(guān)鍵字?jǐn)?shù)多1粪摘，還可以看出結(jié)點(diǎn)內(nèi)關(guān)鍵字都是有序的，并且在同一層中阀湿，左邊結(jié)點(diǎn)內(nèi)所有關(guān)鍵字均小于右邊結(jié)點(diǎn)內(nèi)的關(guān)鍵字赶熟，例如瑰妄，第二層上的兩個(gè)結(jié)點(diǎn)陷嘴，左邊結(jié)點(diǎn)內(nèi)的關(guān)鍵字為15，26间坐，他們均小于右邊結(jié)點(diǎn)內(nèi)的關(guān)鍵字39和45.
B-樹(shù)一個(gè)很重要的特征是灾挨，下層結(jié)點(diǎn)內(nèi)的關(guān)鍵字取值總是落在由上層結(jié)點(diǎn)關(guān)鍵字所劃分的區(qū)間內(nèi)，具體落在哪個(gè)區(qū)間內(nèi)可以由指向它的指針看出竹宋。例如劳澄，第二層最左邊的結(jié)點(diǎn)內(nèi)的關(guān)鍵字劃分了三個(gè)區(qū)間，小于15蜈七，15到26秒拔，大于26，可以看出其下層中最左邊結(jié)點(diǎn)內(nèi)的關(guān)鍵字都小于15飒硅，中間結(jié)點(diǎn)的關(guān)鍵字在15和26之間砂缩，右邊結(jié)點(diǎn)的關(guān)鍵字大于26.
5）上圖中葉子結(jié)點(diǎn)都在第四層上，代表查找不成功的位置三娩。
擴(kuò)展：鏈接：漫畫：什么是B-樹(shù)庵芭？
B+Tree
B-Tree有許多變種，其中最常見(jiàn)的是B+Tree雀监，例如MySQL就普遍使用B+Tree實(shí)現(xiàn)其索引結(jié)構(gòu)双吆。
一個(gè)m階的B+樹(shù)具有如下幾個(gè)特征：
1.有k個(gè)子樹(shù)的中間節(jié)點(diǎn)包含有k個(gè)元素（B樹(shù)中是k-1個(gè)元素），每個(gè)元素不保存數(shù)據(jù)，只用來(lái)索引好乐，所有數(shù)據(jù)都保存在葉子節(jié)點(diǎn)匾竿。
2.所有的葉子結(jié)點(diǎn)中包含了全部元素的信息，及指向含這些元素記錄的指針曹宴，且葉子結(jié)點(diǎn)本身依關(guān)鍵字的大小自小而大順序鏈接搂橙。
3.所有的中間節(jié)點(diǎn)元素都同時(shí)存在于子節(jié)點(diǎn)，在子節(jié)點(diǎn)元素中是最大（或最械烟埂）元素区转。
與B-Tree相比，B+Tree有以下不同點(diǎn)：
內(nèi)節(jié)點(diǎn)不存儲(chǔ)data版扩，只存儲(chǔ)key废离；葉子節(jié)點(diǎn)不存儲(chǔ)指針。
所有葉子節(jié)點(diǎn)形成有序鏈表礁芦，便于范圍查詢蜻韭。
圖3是一個(gè)簡(jiǎn)單的B+Tree示意。
圖3
由于并不是所有節(jié)點(diǎn)都具有相同的域柿扣，因此B+Tree中葉節(jié)點(diǎn)和內(nèi)節(jié)點(diǎn)一般大小不同肖方。這點(diǎn)與B-Tree不同，雖然B-Tree中不同節(jié)點(diǎn)存放的key和指針可能數(shù)量不一致未状，但是每個(gè)節(jié)點(diǎn)的域和上限是一致的俯画，所以在實(shí)現(xiàn)中B-Tree往往對(duì)每個(gè)節(jié)點(diǎn)申請(qǐng)同等大小的空間。
一般來(lái)說(shuō)司草，B+Tree比B-Tree更適合實(shí)現(xiàn)外存儲(chǔ)索引結(jié)構(gòu)艰垂，具體原因與外存儲(chǔ)器原理及計(jì)算機(jī)存取原理有關(guān)，將在下面討論埋虹。
帶有順序訪問(wèn)指針的B+Tree
一般在數(shù)據(jù)庫(kù)系統(tǒng)或文件系統(tǒng)中使用的B+Tree結(jié)構(gòu)都在經(jīng)典B+Tree的基礎(chǔ)上進(jìn)行了優(yōu)化猜憎，增加了順序訪問(wèn)指針。
圖4
如圖4所示搔课，在B+Tree的每個(gè)葉子節(jié)點(diǎn)增加一個(gè)指向相鄰葉子節(jié)點(diǎn)的指針胰柑，就形成了帶有順序訪問(wèn)指針的B+Tree。做這個(gè)優(yōu)化的目的是為了提高區(qū)間訪問(wèn)的性能爬泥，例如圖4中如果要查詢key為從18到49的所有數(shù)據(jù)記錄柬讨，當(dāng)找到18后，只需順著節(jié)點(diǎn)和指針順序遍歷就可以一次性訪問(wèn)到所有數(shù)據(jù)節(jié)點(diǎn)急灭，極大提到了區(qū)間查詢效率姐浮。
這一節(jié)對(duì)B-Tree和B+Tree進(jìn)行了一個(gè)簡(jiǎn)單的介紹，下一節(jié)結(jié)合存儲(chǔ)器存取原理介紹為什么目前B+Tree是數(shù)據(jù)庫(kù)系統(tǒng)實(shí)現(xiàn)索引的首選數(shù)據(jù)結(jié)構(gòu)葬馋。
擴(kuò)展：鏈接：漫畫：什么是B 樹(shù)卖鲤？
參考文獻(xiàn)
[0] http://blog.codinglabs.org/articles/theory-of-mysql-index.html
[1] Baron Scbwartz等 著肾扰，王小東等 譯；高性能MySQL（High Performance MySQL）蛋逾；電子工業(yè)出版社集晚，2010
[2] Michael Kofler 著，楊曉云等 譯区匣；MySQL5權(quán)威指南（The Definitive Guide to MySQL5）偷拔；人民郵電出版社，2006
[3] 姜承堯 著亏钩；MySQL技術(shù)內(nèi)幕-InnoDB存儲(chǔ)引擎莲绰；機(jī)械工業(yè)出版社，2011
[4] D Comer, Ubiquitous B-tree; ACM Computing Surveys (CSUR), 1979
[5] Codd, E. F. (1970). "A relational model of data for large shared data banks". Communications of the ACM, , Vol. 13, No. 6, pp. 377-387
[6] MySQL5.1參考手冊(cè) - http://dev.mysql.com/doc/refman/5.1/zh/index.html
