M為樹的階數(shù)疲吸，B-樹或?yàn)榭諛涓焕埃駝t滿足下列條件：
對(duì)于一棵M階的B-樹
- 任意非葉子結(jié)點(diǎn)最多只有M個(gè)兒子琉朽；且M>2淤袜；
- 根結(jié)點(diǎn)的兒子數(shù)為[2, M]痒谴；
- 除根結(jié)點(diǎn)以外的非葉子結(jié)點(diǎn)的兒子數(shù)為[M/2, M]；
- 每個(gè)結(jié)點(diǎn)存放至少M(fèi)/2-1（取上整）和至多M-1個(gè)關(guān)鍵字铡羡；（至少2個(gè)關(guān)鍵字,根節(jié)點(diǎn)至少一個(gè)關(guān)鍵字）积蔚；
- 非葉子結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)=指向兒子的指針個(gè)數(shù)-1；
- 非葉子結(jié)點(diǎn)的關(guān)鍵字：K[1], K[2], …, K[m-1]烦周，m<M+1尽爆；且K[i]< K[i+1] ；
- 非葉子結(jié)點(diǎn)的指針：P[1], P[2], …, P[m]读慎；其中P[1]指向關(guān)鍵字小于K[1]的子樹漱贱，P[m]指向關(guān)鍵字大于K[m-1]的子樹，其它P[i]指向關(guān)鍵字屬于(K[i-1], K[i])的子樹夭委；
- 所有葉子結(jié)點(diǎn)位于同一層幅狮；
如：（M=3）
B-樹.jpg
B+樹是文件系統(tǒng)所需而出的一種B-樹的變型樹。一棵m階的B+樹和m階的B-樹的差異在于：
- 有k個(gè)子結(jié)點(diǎn)的結(jié)點(diǎn)必然有k個(gè)關(guān)鍵碼株灸；
- 非葉結(jié)點(diǎn)僅具有索引作用崇摄，和記錄有關(guān)的信息均存放在葉結(jié)點(diǎn)中。
-
樹的所有葉結(jié)點(diǎn)構(gòu)成一個(gè)有序鏈表慌烧，可以按照關(guān)鍵碼排序的次序遍歷全部記錄逐抑。
通常在B+樹上有兩個(gè)頭指針，一個(gè)指向根結(jié)點(diǎn)屹蚊，一個(gè)指向關(guān)鍵字最小的葉子結(jié)點(diǎn)厕氨。
B+樹
B和B+樹的區(qū)別在于，B+樹的非葉子結(jié)點(diǎn)只包含導(dǎo)航信息汹粤，不包含實(shí)際的值命斧，所有的葉子結(jié)點(diǎn)和相連的節(jié)點(diǎn)使用鏈表相連，便于區(qū)間查找和遍歷玄括。
B+ 樹的優(yōu)點(diǎn)在于：
由于B+樹在內(nèi)部節(jié)點(diǎn)上不包含數(shù)據(jù)信息冯丙，因此在內(nèi)存頁(yè)中能夠存放更多的key肉瓦。 因此訪問(wèn)葉子節(jié)點(diǎn)上關(guān)聯(lián)的數(shù)據(jù)也具有更好的緩存命中率遭京。
B+樹的葉子結(jié)點(diǎn)都是相鏈的，因此對(duì)整棵樹只需要一次線性遍歷葉子結(jié)點(diǎn)即可泞莉。而且由于數(shù)據(jù)順序排列并且相連哪雕，所以便于區(qū)間查找和搜索。而B樹則需要進(jìn)行每一層的遞歸遍歷鲫趁。相鄰的元素可能在內(nèi)存中不相鄰斯嚎，所以緩存命中性沒(méi)有B+樹好。
但是B樹也有優(yōu)點(diǎn)，其優(yōu)點(diǎn)在于堡僻，由于B樹的每一個(gè)節(jié)點(diǎn)都包含key和value糠惫，因此經(jīng)常訪問(wèn)的元素可能離根節(jié)點(diǎn)更近，因此訪問(wèn)也更迅速钉疫。
