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)也更迅速钉疫。