B樹

1970年，R.Bayer和E.mccreight提出了一種適用於外查找的樹，它是一種平衡的多叉樹，稱為B樹（或B-樹、B_樹）。

一棵m階B樹(balanced tree of order m)是一棵平衡的m路搜索樹。它或者是空樹，或者是滿足下列性質的樹：

1、根結點至少有兩個子女；

2、每個非根節點所包含的關鍵字個數 j 滿足：┌m/2┐ - 1 <= j <= m - 1；

3、除根結點以外的所有結點（不包括葉子結點）的度數正好是關鍵字總數加1，故內部子樹個數 k 滿足：┌m/2┐ <= k <= m ；

4、所有的葉子結點都位於同一層。

在B-樹中，每個結點中關鍵字從小到大排列，並且當該結點的孩子是非葉子結點時，該k-1個關鍵字正好是k個孩子包含的關鍵字的值域的分劃。

因為葉子結點不包含關鍵字，所以可以把葉子結點看成在樹裏實際上並不存在外部結點，指向這些外部結點的指針為空，葉子結點的數目正好等於樹中所包含的關鍵字總個數加1。

B-樹中的一個包含n個關鍵字，n+1個指針的結點的一般形式為： （n,P0,K1,P1,K2,P2,…,Kn,Pn）

其中，Ki為關鍵字，K1<K2<…<Kn, Pi 是指向包括Ki到Ki+1之間的關鍵字的子樹的指針。

設B-樹包含N個關鍵字，因此有N+1個葉子結點，葉子都在第I層。因為根至少有兩個孩子，因此第二層至少有兩個結點。除根和葉子外，其它結點至少有┌m/2┐個孩子，因此在第三層至少有2*┌m/2┐個結點，在第四層至少有2*(┌m/2┐^2)個結點，．．．，在第I層至少有2*(┌m/2┐^(l-2) )個結點，於是有：

N+1 ≥ 2*┌m/2┐I-2

考慮第L層的結點個數為N+1，那麼2*(┌m/2┐^(l-2)）≤N+1，也就是L層的最少結點數剛好達到N+1個

即： I≤ log┌m/2┐((N+1)/2 )+2

所以，當B-樹包含N個關鍵關鍵字時，B-樹的最大高度為l-1（因為計算B-樹高度時，葉結點所在層不計算在內）

即：log┌m/2┐((N+1)/2 )+1。

這個公式保證了B-樹的查找效率是相當高的。

當在葉子結點處於第L+1層的B樹中插入關鍵字時，被插入的關鍵字總是進入第L層的結點。

若在一個包含j<m-1個關鍵字的結點中插入一個新的關鍵字，則把新的關鍵字直接插入該結點即可；但若把一個新的關鍵字插入到包含m-1（m為B-樹的階）個關鍵字的結點中，則將引起結點的分裂。在這種情況下，要把這個結點分裂為兩個，並把中間的一個關鍵字（中間的關鍵字滿足：左邊的小於該關鍵字；右邊的大於該關鍵字；故正好可以作為雙親）拿出來插到該結點的雙親結點中去，雙親結點也可能是滿的，就需要再分裂、再往上插，從而可能導致B-樹可能朝着根的方向生長。

插入算法演示：插入之前如圖1：

插入之後如圖2：

4. B-樹的刪除:

當從B-樹中刪除一個關鍵字Ki時，總的分為以下兩種情況：

如果該關鍵字所在的結點不是最下層的非葉子結點，則先需要把此關鍵字與它在B-樹中後繼對換位置，即以指針Pi所指子樹中的最小關鍵字Y代替Ki，然後在相應的結點中刪除Y。

如果該關鍵字所在的結點正好是最下層的非葉子結點，這種情況下，會有以下兩種可能：

① 若該關鍵字Ki所在結點中的關鍵字個數不小於┌m/2┐，則可以直接從該結點中刪除該關鍵字和相應指針即可。

② 若該關鍵字Ki所在結點中的關鍵字個數小於┌m/2┐，則直接從結點中刪除關鍵字會導致此結點中所含關鍵字個數小於┌m/2┐-1 。這種情況下，需考察該結點在B樹中的左或右兄弟結點，從兄弟結點中移若干個關鍵字到該結點中來（這也涉及它們的雙親結點中的一個關鍵字要作相應變化），使兩個結點中所含關鍵字個數基本相同；但如果其兄弟結點的關鍵字個數也很少，剛好等於┌m/2┐-1 ，這種移動則不能進行，這種情形下，需要把刪除了關鍵字Ki的結點、它的兄弟結點及它們雙親結點中的一個關鍵字合併為一個結點。