什么是B樹

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

4階B樹.png

B樹具有以下特點：

1. 一個節(jié)點可以存儲超過2個元素，一個節(jié)點可以擁有超過兩個子節(jié)點；
2. 擁有二叉搜索樹的一些性質(zhì)；
3. 平衡，每個節(jié)點的所有子樹高度一致
4. B樹比較矮

m階B樹的性質(zhì)（m>=2）

假設一個節(jié)點存儲的元素個數(shù)為x，

1. 根節(jié)點： 1 <= x <= m-1
2. 非根節(jié)點：? m/2 ? -1 <=x <= m-1
3. 如果有子節(jié)點，子節(jié)點個數(shù) y = x+1
   a. 根節(jié)點：1 <= y <= m
   b. 非根節(jié)點：? m/2 ? <= y <= m
   比如，m=3，1 <= y< = 3，因此可以稱為（2, 3）樹、2-3樹；
   再如，m=4 ,2 <= y <= 4，因此可以稱為（2, 4）樹、2-3-4樹；
   再如，m=5 ,3 <= y <= 5，因此可以稱為（3, 5）樹；
   再如，m=6 ,3 <= y <= 6，因此可以稱為（3, 6）樹；
   再如，m=7 ,4 <= y <= 7，因此可以稱為（4, 7）樹。

B樹與二叉搜索樹

1. 對于m階B樹，m=2就是二叉搜索樹。B樹與二叉搜索樹在邏輯上是等價的；
2. 多代節(jié)點合并，可以獲得一個超級節(jié)點，比如：
   兩代合并的超級節(jié)點，最多擁有4個子節(jié)點（至少是4階B樹），
   三代合并的超級節(jié)點，最多擁有8個子節(jié)點（至少是8階B樹），
   n代合并的超級節(jié)點，最多擁有2^{n個子節(jié)點（至少是2}n階B樹）
3. m階B樹，最多需要logm代合并

B樹的搜索

與二叉樹搜索類似，

1. 先在節(jié)點內(nèi)部從小到大開始搜索元素；
2. 如果命中，搜索結束；
3. 如果未命中，再去對應的子節(jié)點中搜索元素，重復步驟1

B樹的元素添加

4階B樹添加元素.png

1. 新添加的元素必定是添加到葉子節(jié)點【這個是B樹的性質(zhì)】
2. 添加元素，元素個數(shù)可能會高于最大限制（要求的最大限制是 m-1），造成“上溢（overflow）”
3. 上溢的解決：
   上溢節(jié)點的元素個數(shù)必然等于m，假設上溢節(jié)點最中間元素的位置為k，
   a. 將k位置的元素向上與父節(jié)點合并；
   b. 將[0, k-1] 和 [k+1, m-1] 位置的元素分裂成2個子節(jié)點。這2個子節(jié)點的元素個數(shù)，必然都不會低于最低限制 ?m/2?-1
   c. 一次分裂完成后，有可能導致父節(jié)點上溢，依然按照上述方法解決
   上溢的解決又可能讓B樹變高。

B樹的元素刪除

4階B樹刪除元素.png

1. 如果需要刪除的元素在葉子節(jié)點中，那么直接刪除即可；

2. 如果需要刪除的元素在非葉子節(jié)點中：
   a. 先找到前驅或后繼元素，覆蓋所要刪除的元素的值
   b. 再把前驅或后繼元素刪除
   注意：非葉子節(jié)點的前驅或后繼元素，必定在葉子節(jié)點中。所以這里的刪除前驅或后繼元素，就是步驟1中的情況，刪除的元素在葉子節(jié)點中。也就是說，真正的刪除元素都是發(fā)生在葉子節(jié)點中。

3. 葉子節(jié)點被刪除掉一個元素后，元素個數(shù)可能會低于最低限制（要求的最低限制是 ?m/2?-1），就會出現(xiàn)“下溢（underflow）”。

4. “下溢”的解決：
   下溢節(jié)點的元素數(shù)量必然等于：?m/2?-2
   a. 如果下溢節(jié)點臨近的兄弟節(jié)點，有至少?m/2? 個元素，可以向其借一個元素：1. 將父節(jié)點的元素b插入到下溢節(jié)點的0位置出（最小值所在位置）；2. 用兄弟節(jié)點的元素a（最大的元素）替代父節(jié)點的元素b；這種操作其實就是旋轉。

   看兄弟節(jié)點滿足否.png
   從兄弟節(jié)點借.png
   b. 如果下溢節(jié)點臨近的兄弟節(jié)點，只有 ?m/2?-1個元素：1. 將父節(jié)點的元素b挪下來跟左右子節(jié)點進行合并；2. 合并后的節(jié)點元素個數(shù)等于?m/2?+?m/2? -2，不超過m-1
   兄弟節(jié)點不滿足.png

挪動父節(jié)點.png

c. 這個操作可能會導致父節(jié)點下溢，依然按照上述方法解決，下溢現(xiàn)象可能會一直往上傳播，可以讓B樹變矮。