1.B-數(shù)、B+數(shù)

B-樹

特點(diǎn)：

是一種多路搜索樹（并不是二叉的）：

1.定義任意非葉子結(jié)點(diǎn)最多只有M個(gè)兒子笆怠；且M>2铝耻；

2.根結(jié)點(diǎn)的兒子數(shù)為[2, M]誊爹；

3.除根結(jié)點(diǎn)以外的非葉子結(jié)點(diǎn)的兒子數(shù)為[M/2, M]蹬刷；

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

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

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

7.非葉子結(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])的子樹；

8.所有葉子結(jié)點(diǎn)位于同一層而克；

如：（M=3）

B-樹的搜索靶壮，從根結(jié)點(diǎn)開始，對結(jié)點(diǎn)內(nèi)的關(guān)鍵字（有序）序列進(jìn)行二分查找员萍，如果

命中則結(jié)束腾降，否則進(jìn)入查詢關(guān)鍵字所屬范圍的兒子結(jié)點(diǎn)；重復(fù)碎绎，直到所對應(yīng)的兒子指針為空螃壤，或已經(jīng)是葉子結(jié)點(diǎn)；

B-樹的特性：

1.關(guān)鍵字集合分布在整顆樹中筋帖；

2.任何一個(gè)關(guān)鍵字出現(xiàn)且只出現(xiàn)在一個(gè)結(jié)點(diǎn)中奸晴；

3.搜索有可能在非葉子結(jié)點(diǎn)結(jié)束；

4.其搜索性能等價(jià)于在關(guān)鍵字全集內(nèi)做一次二分查找日麸；

5.自動層次控制寄啼；

B+樹

B+ 樹是一種樹數(shù)據(jù)結(jié)構(gòu)，是一個(gè)n叉樹代箭，每個(gè)節(jié)點(diǎn)通常有多個(gè)孩子辕录，一棵B+樹包含根節(jié)點(diǎn)、內(nèi)部節(jié)點(diǎn)和葉子節(jié)點(diǎn)梢卸。根節(jié)點(diǎn)可能是一個(gè)葉子節(jié)點(diǎn)走诞，也可能是一個(gè)包含兩個(gè)或兩個(gè)以上孩子節(jié)點(diǎn)的節(jié)點(diǎn)。

用途：

B+ 樹通常用于數(shù)據(jù)庫和操作系統(tǒng)的文件系統(tǒng)中蛤高。NTFS, ReiserFS, NSS, XFS, JFS, ReFS 和BFS等文件系統(tǒng)都在使用B+樹作為元數(shù)據(jù)索引蚣旱。B+ 樹的特點(diǎn)是能夠保持?jǐn)?shù)據(jù)穩(wěn)定有序，其插入與修改擁有較穩(wěn)定的對數(shù)時(shí)間復(fù)雜度戴陡。B+ 樹元素自底向上插入塞绿。

B+樹的定義

B+樹是應(yīng)文件系統(tǒng)所需而出的一種B-樹的變型樹。一棵m階的B+樹和m階的B-樹的差異在于：

1.有n棵子樹的結(jié)點(diǎn)中含有n個(gè)關(guān)鍵字恤批，每個(gè)關(guān)鍵字不保存數(shù)據(jù)异吻，只用來索引，所有數(shù)據(jù)都保存在葉子節(jié)點(diǎn)。

2.所有的葉子結(jié)點(diǎn)中包含了全部關(guān)鍵字的信息诀浪，及指向含這些關(guān)鍵字記錄的指針棋返，且葉子結(jié)點(diǎn)本身依關(guān)鍵字的大小自小而大順序鏈接。

3.所有的非終端結(jié)點(diǎn)可以看成是索引部分雷猪，結(jié)點(diǎn)中僅含其子樹（根結(jié)點(diǎn)）中的最大（或最芯ⅰ）關(guān)鍵字。

通常在B+樹上有兩個(gè)頭指針求摇，一個(gè)指向根結(jié)點(diǎn)射沟，一個(gè)指向關(guān)鍵字最小的葉子結(jié)點(diǎn)。

B+樹是B-樹的變體与境，也是一種多路搜索樹：

1.其定義基本與B-樹同验夯，除了：

2.非葉子結(jié)點(diǎn)的子樹指針與關(guān)鍵字個(gè)數(shù)相同；

3.非葉子結(jié)點(diǎn)的子樹指針P[i]摔刁，指向關(guān)鍵字值屬于[K[i], K[i+1])的子樹（B-樹是開區(qū)間）簿姨；

5.為所有葉子結(jié)點(diǎn)增加一個(gè)鏈指針；

6.所有關(guān)鍵字都在葉子結(jié)點(diǎn)出現(xiàn)簸搞；

如：（M=3）

B+的搜索與B-樹也基本相同扁位，區(qū)別是B+樹只有達(dá)到葉子結(jié)點(diǎn)才命中（B-樹可以在

非葉子結(jié)點(diǎn)命中），其性能也等價(jià)于在關(guān)鍵字全集做一次二分查找趁俊；

B+的特性：

1.所有關(guān)鍵字都出現(xiàn)在葉子結(jié)點(diǎn)的鏈表中（稠密索引）域仇，且鏈表中的關(guān)鍵字恰好是有序的；

2.不可能在非葉子結(jié)點(diǎn)命中寺擂；

3.非葉子結(jié)點(diǎn)相當(dāng)于是葉子結(jié)點(diǎn)的索引（稀疏索引）暇务，葉子結(jié)點(diǎn)相當(dāng)于是存儲（關(guān)鍵字）數(shù)據(jù)的數(shù)據(jù)層；

4.更適合文件索引系統(tǒng)怔软；

紅黑樹待續(xù)...