1、前言

B樹是為磁盤或其它直接存取的輔助存儲設(shè)備而設(shè)計的一種平衡搜索樹，它類似于紅黑樹，但它在降低磁盤I/O操作上更好，B樹也常被用于數(shù)據(jù)庫中。

B樹的最大不同之處在于B樹的結(jié)點可以有很多孩子，數(shù)十到數(shù)千都可以。因為此特性，B樹的高度一般會比紅黑樹低很多。

ps：有種觀點是B樹即為普通二叉搜索樹，B-樹才是本文中討論的B樹，本文不采納此觀點，B-樹是從B-Tree翻譯過來的，翻譯成B-樹，這也太粗糙了。

2、B樹定義

從上圖可知，B樹結(jié)點中，如果有n個關(guān)鍵字，那么就有n+1個孩子。結(jié)點x中的關(guān)鍵字就是分隔點，分隔成n+1個子域。

每個結(jié)點x都有以下屬性：

• x.n，當(dāng)前存儲在結(jié)點x中的關(guān)鍵字個數(shù)
• x.n個關(guān)鍵字本身x.key₁，x.key₂，x.key_x.n，以非降序存放，使得x.key₁<=x.key₂<=...<=x.key_x.n
• x.leaf，一個布爾值，如果x是葉結(jié)點，則為true，如果是內(nèi)部結(jié)點，則為false
• 每個內(nèi)部結(jié)點x還包含 x.n+1 個指向其孩子的指針，x.c₁，x.c₂，x.c_x.n+1，葉結(jié)點沒有孩子，所以它們的c_i屬性沒有定義。
• 關(guān)鍵字x.key_i對存儲在各子樹中的關(guān)鍵字范圍加以分割，如果k_i為任意一個存儲在以 x.c_i 為根的子樹的關(guān)鍵字，那么：
  k₁ <= x.key₁ <= k₂ <= x.key₂ <= ... <= x.key_x.n <= k_x.n+1
• 每個葉結(jié)點具有相同的深度，即樹的高度h
• 每個結(jié)點所包含的關(guān)鍵字個數(shù)有上界和下界。用一個被稱為B樹的最小度數(shù)的固定整數(shù) t>=2 來表示界。
• 除了根結(jié)點以外的每個結(jié)點必須至少有t-1個關(guān)鍵字，因此除了根結(jié)點以外的每個內(nèi)部結(jié)點至少有t個孩子。如果樹非空，根結(jié)點至少有一個關(guān)鍵字
• 每個結(jié)點最多可包含 2t -1 個關(guān)鍵字，因為一個內(nèi)部結(jié)點至多有2t 個孩子，當(dāng)一個結(jié)點有 2t-1 個關(guān)鍵字時，該結(jié)點是滿的

B樹的屬性有點多，尤其是最后兩點，注意是除根結(jié)點以外的每個結(jié)點最少有t-1個關(guān)鍵字，并不是所有結(jié)點都是。

B樹的特色或者精髓就在于每個結(jié)點的子結(jié)點非常多，在樹高非常低的情況下就能存儲大數(shù)數(shù)據(jù)。B樹高度有以下定理

3、向B樹中插入關(guān)鍵字

在普通二叉搜索樹中，插入關(guān)鍵字，一定會新增加一個節(jié)點。但在B樹中，不能簡單地創(chuàng)建一個新的節(jié)點，新增的關(guān)鍵字一定是被插入已經(jīng)存在的葉結(jié)點上。

如果被插入的葉結(jié)點已滿，它的關(guān)鍵字個數(shù)為 2t-1 個，此時需要分裂結(jié)點。如圖：

結(jié)點分裂是指，將一個滿結(jié)點，按其中間關(guān)鍵字y.key_t分裂成兩個各含t-1個關(guān)鍵字的結(jié)點，中間關(guān)鍵字被提升到y(tǒng)的父結(jié)點。如果y的父結(jié)點也是滿的怎么辦呢？將y的父結(jié)點也分裂即可。

/**
 * @param x 被分裂結(jié)點的父結(jié)點
 * @param i 被分列結(jié)點在父結(jié)點中的index
 * 分裂算法并不復(fù)雜，自己繪圖，搞清楚上界下界，具體index等就可以了
 */
public static void btreeSplitChild(BNode x, int i){
    BNode z = new BNode();
    BNode y = x.c[i];
    //z為分裂得到的新結(jié)點
    z.leaf = y.leaf;
    z.n = t - 1;
    //將被分裂結(jié)點的后一半關(guān)鍵字復(fù)制給z，同時刪除后一半關(guān)鍵字
    for (int j = 0; j < t-1; j++) {
        z.k[j] = y.k[j+t];
        y.k[j+t] = Integer.MIN_VALUE;
    }
    //將被分裂結(jié)點的后一半子結(jié)點復(fù)制給z，同時置空后一半子結(jié)點
    if (!y.leaf) {
        for (int j = 0; j < t; j++) {
            z.c[j] = y.c[j+t];
            y.c[j+t] = null;
        }
    }
    y.n = t-1;
    //后移一位x的關(guān)鍵字，給分裂上來的新關(guān)鍵字騰位置
    for (int j = x.n-1; j >= i; j--) {
        x.k[j+1] = x.k[j];
    }
    x.k[i] = y.k[t-1];
    y.k[t-1] = Integer.MIN_VALUE;
    //后移一位x的子結(jié)點，給分裂新增加的子結(jié)點騰位置
    for (int j = x.n; j >= i+1; j--) {
        x.c[j+1] = x.c[j];
    }
    x.c[i+1] = z;
    x.n = x.n+1;
}

到目前為止，提煉給B樹插入新元素的三個關(guān)鍵點：

• 元素一定是插入在葉結(jié)點上的

• 如果在查找過程中，路徑上的某個結(jié)點為滿結(jié)點，分裂它

• B樹的高度增加只能通過分裂增長，通常是分裂根節(jié)點實現(xiàn)高度增長，而不能隨便添加葉結(jié)點來增高，否則會違反B樹性質(zhì)

  public static void btreeInsertNotFull(BNode x, int k){
    int i = x.n - 1;
    if (x.leaf) {
        //如果是葉結(jié)點，根據(jù)關(guān)鍵字大小排序，找出k的位置即可
        while (x.n > 0 && i >= 0 && k < x.k[i]) {
            x.k[i+1] = x.k[i];
            i--;
        }
        x.k[i+1] = k;
        x.n = x.n + 1;
    }else {
        //如果是內(nèi)部結(jié)點，找出k對應(yīng)的子樹區(qū)域
        while (x.n > 0 && i >= 0 && k < x.k[i]) {
            i= i-1;
        }
        i = i+1;
        //如果路徑中有某個結(jié)點是滿結(jié)點，分裂它
        if (x.c[i].n == 2*t - 1) {
            btreeSplitChild(x, i);
            if (k > x.k[i]) {
                i = i+1;
            }
        }
        //再次在子樹中遞歸插入
        btreeInsertNotFull(x.c[i], k);
    }
  }
  

4、B樹查找

B樹查找非常簡單，先在當(dāng)前結(jié)點中找不大于k的關(guān)鍵字，如果相等則返回，如果不相等，則去對應(yīng)的子結(jié)點中，遞歸查找。

public static void find(BNode x, int k){
    int i = 0;
    while (x.n > 0 && k > x.k[i]) {
        i++;
    }
    if (i < x.n && k == x.k[i]) {
        x.print();
        System.out.println(i);
        return;
    }
    if (x.leaf) {
        System.out.println("no result");
        return;
    }
    find(x.c[i], k);
}

關(guān)于B樹刪除，比插入還要復(fù)雜一些，詳情可看算法導(dǎo)論一書，本文暫時不添加這部分內(nèi)容，后續(xù)再研究。