何為B樹(shù)？B樹(shù)是一種平衡的多路搜索樹(shù)，多用于文件系統(tǒng)，數(shù)據(jù)庫(kù)的實(shí)現(xiàn)

下面上幾張B樹(shù)圖：

3階

4階

5階

從B樹(shù)圖中可以看出一些特點(diǎn)：1個(gè)節(jié)點(diǎn)可以存儲(chǔ)超過(guò)2個(gè)元素，可以擁有超過(guò)2個(gè)子節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)的所有紫薯高度一致

m階B樹(shù)的性質(zhì)()

假設(shè)一個(gè)節(jié)點(diǎn)存儲(chǔ)的元素個(gè)數(shù)為x

如果該節(jié)點(diǎn)是根節(jié)點(diǎn)：,如果是非根節(jié)點(diǎn)，如果有子節(jié)點(diǎn)，子節(jié)點(diǎn)個(gè)數(shù)y=x + 1；那根節(jié)點(diǎn)的子節(jié)點(diǎn)個(gè)數(shù),非根節(jié)點(diǎn)的的個(gè)數(shù)：

B樹(shù)VS二叉搜索樹(shù)

二叉搜索樹(shù)

3階B樹(shù)

可以發(fā)現(xiàn)B樹(shù)和二叉搜索樹(shù)，在邏輯上是等價(jià)的，可以這樣理解3階B樹(shù)是由二叉搜索樹(shù)2～n代合并組成的，于是由下面這樣一些性質(zhì)：

2代合并的超級(jí)節(jié)點(diǎn)，最多擁有4個(gè)子節(jié)點(diǎn)(至少是4階B樹(shù))，3代合并的超級(jí)節(jié)點(diǎn)，最多擁有8個(gè)子節(jié)點(diǎn)(至少是8階B樹(shù))，n代合并的超級(jí)節(jié)點(diǎn)，最多擁有個(gè)子節(jié)點(diǎn)（至少是階B樹(shù)），m階B樹(shù)，最多需要代合并

B樹(shù)搜索

1.現(xiàn)在節(jié)點(diǎn)內(nèi)部從小到大開(kāi)始搜索元素

2.如果命中，搜索結(jié)束

3.如果未命中，再去對(duì)應(yīng)的子節(jié)點(diǎn)中搜索元素，重復(fù)步驟1

B樹(shù)添加

新添加的元素必定是添加到葉子節(jié)點(diǎn)的（從上面往下比，然后一直到最后）

示例圖

假如現(xiàn)在插入55

插入55

但是這里你會(huì)發(fā)現(xiàn)，如果所有葉子節(jié)點(diǎn)都達(dá)到飽和的情況下，或者要添加的那個(gè)葉子節(jié)點(diǎn)達(dá)到飽和的時(shí)候，就會(huì)出現(xiàn)一個(gè)問(wèn)題節(jié)點(diǎn)上溢

添加-上溢的解決（假設(shè)5階）

從前面可以知道一個(gè)性質(zhì)，就是如果B樹(shù)發(fā)生上益那么上溢節(jié)點(diǎn)的元素個(gè)數(shù)必然等于m，上溢的解決方式如下：

假設(shè)上溢節(jié)點(diǎn)最中間的元素位置為k，將k位置的元素向上與父節(jié)點(diǎn)合并，然后將[0,k-1]和[k+1,m-1]位置的元素分類成2個(gè)子節(jié)點(diǎn)，這2個(gè)子節(jié)點(diǎn)的元素個(gè)數(shù)，必然都不會(huì)低于最低限制（ceil(m/2)-1),如果一次分類完畢后，有可能導(dǎo)致父節(jié)點(diǎn)上溢，依然按照上面說(shuō)的方式解決，一層一層往上處理，最極端的情況，就是有可能一直分裂到根節(jié)點(diǎn)；給個(gè)展示圖：

上溢處理圖

再示范多一個(gè)添加過(guò)程圖：

B樹(shù)添加

B樹(shù)刪除

刪除分葉子節(jié)點(diǎn)刪除和非葉子節(jié)點(diǎn)刪除，如果需要?jiǎng)h除的元素在葉子節(jié)點(diǎn)，那么直接刪除就可以了例如下面圖：

刪除葉子節(jié)點(diǎn)

如果刪除的是非葉子節(jié)點(diǎn)，那么就要先找到前驅(qū)或后繼元素，覆蓋所需刪除元素的值，再把前驅(qū)或后繼元素刪除，如下圖：

刪除非葉子節(jié)點(diǎn)

從圖中可以得出結(jié)論：非葉子節(jié)點(diǎn)的前驅(qū)或后繼元素，必定在葉子節(jié)點(diǎn)中，真正刪除的元素都是發(fā)生在葉子節(jié)點(diǎn)中；

但是刪除節(jié)點(diǎn)有可能會(huì)導(dǎo)致下溢情況的出現(xiàn)，例如下面這種情形：

下溢

假設(shè)上面這個(gè)圖是一棵5階B樹(shù)，那么如果刪掉元素22之后，元素個(gè)數(shù)可能就會(huì)低于最低限制(),這個(gè)時(shí)候我們就要解決下溢的問(wèn)題了

刪除-下溢的解決

下溢節(jié)點(diǎn)的元素?cái)?shù)量必然等于ceil(m/2)-2，如果這個(gè)時(shí)候下溢節(jié)點(diǎn)臨近的兄弟節(jié)點(diǎn)，有至少ceil(m/2)個(gè)元素，可以向其借一個(gè)元素，如下圖：

下溢1

但是如果下溢節(jié)點(diǎn)臨近的兄弟節(jié)點(diǎn)，只有ceil(m/2)-1個(gè)元素呢？這個(gè)時(shí)候我們需要從父節(jié)點(diǎn)中挪取元素下來(lái)跟左右子節(jié)點(diǎn)進(jìn)行合并，合并后的節(jié)點(diǎn)元素個(gè)數(shù)等于ceil(m/2)+ceil(m/2)-2,不超過(guò)m-1,但是這個(gè)操作可能會(huì)導(dǎo)致父節(jié)點(diǎn)下溢，依然按照上述方法解決，下溢現(xiàn)象可能會(huì)一直往上傳播，示例圖：

下溢2

舉一個(gè)例子說(shuō)明展示實(shí)際情況：

刪除例子

B樹(shù)大概就學(xué)習(xí)到這里先吧，后續(xù)如果我還能學(xué)到新的東西的時(shí)候再補(bǔ)充吧