淺析B樹基本算法

B樹簡介

B樹，是為磁盤或其他直接存取輔助存儲設備二設計的一種平衡查找樹，由于它的特殊結構，可以大大減少訪問磁盤I/O的次數，因此在數據庫系統常使用Ｂ數或Ｂ樹的變形來存儲信息。

Ｂ樹滿足某種條件，與紅黑樹或其他搜索樹不同，一棵M（M>2）的B樹，是一棵M路的平衡搜索樹，它允許有多條分支子樹，它可以是一條空樹，或者滿足以下性質：

1、根節點至少有兩個孩子

2、每個非根節點有[ M/2，M ]個孩子

3、每個非根節點有[ (M/2) -1，M-1 ]個關鍵字，并且以升序排序

4、key[i]和key[i+1]之間的孩子節點的值介于兩者之間

5、所有的葉子節點都在同一層

B樹是一棵向上生長的樹，當一個節點中的關鍵字個數達到上限之后，會進行分裂，同時會向上產生一個新的節點，分裂得到兩個子節點和一個父節點，父節點只有原來節點中的中間key值，兩個子節點將平分原來節點中剩下的key和孩子。這些原因使得B樹滿足上述條件2~5。接下來看張圖，理解一下B樹是如何生長的。    沒有完全看明白先放下，這里只需要知道B樹是一棵多路的平衡搜索樹。在樹不為空樹的前提下，如果M=2，那么所有節點內最多會有M-1個關鍵字key值，每個節點都會有M個孩子。在一個節點內，關鍵字是從小到大排列的，關鍵字和孩子是插空分布的，這也保證了B樹的平衡搜索性。

接下來通過B樹的基本算法來了解一下樹。

B樹算法

    關鍵字：分裂算法、插入算法、查找算法、中序遍歷算法

    首先，根據上述B樹的要求，這里給出一張B樹的示意圖（M=3）

    上面說過，M表示的是每個結點孩子的個數，但是很明顯，在上圖中，孩子給出了4個，那么對應的關鍵字會有3個，和一開始的理論不相符。這里需要說明一下，因為每次向B樹中插入節點之后，會進行判斷，該節點的關鍵字個數是否超過了M，如果超過，我們需要進行分裂算法（后面會提到）。

經過簡單分析，這里給出B樹的節點的定義及構造函數。

template <typename K,int M>
struct BTreeNode
{
    K _key[M];//關鍵字數組
    BTreeNode<K,M>* _sub[M+1];//指向孩子節點的指針數組
    BTreeNode<K,M>* _parent;//指向父節點的指針
    size_t _size; //該節點中已經插入的關鍵字的個數
    BTreeNode()
        :_parent(NULL)
        ,_size(0)
    {
        size_t i = 0;
        for(i = 0; i < M; i++)
        {
            _key[i] = K();
            _sub[i] = NULL;
        }
        _sub[i] = NULL;
    }
}

第一步：查找算法 Find()

    為什么這里要先來實現B樹的查找呢？因為對一棵樹的查找來說，并不會影響到樹的結構，另外，通過查找，也可以幫助我們得到一些其他的更有利的信息，方便其他功能的實現。

    以上面給出的B樹為例，在B樹中查找一個結點，和普通的平衡樹基本思路一樣，比該點的key大就向右查找，比該點的key值小，就向左查找。只不過對于B樹而言，每個節點有M-1個關鍵字。因此在向下查找的同時，需要對每個節點中的每個key進行比較。

由于每個節點這里有M個關鍵字，下標從0~M-1，每個節點有M+1個孩子，指針數組的下標從0~M，仔細觀察上樹，對于某個節點node而言，比節點中的某個key小的一個值，下一次查找的孩子應該和該key的下標相同。

還需要注意的一點，就是我這里的Find函數是希望能夠被其他函數使用的，不僅僅是希望得到一個bool值或找到的Node*，在這里設計Find函數，是希望當找到該key值的話返回key所在節點的下標，同時返回一個指向該節點的指針；沒有找到返回 -1，同時返回該節點應該所在位置的父節點。初衷很簡單，是為了給待會需要實現的Insert函數調用，達到代碼的復用性。如果我們只是判斷該節點在不在B樹內，那對返回值我們就只需要關注bool即可。要實現返回兩個參數，有兩種思路：第一就是通過函數傳參數的方式，傳遞引用達到目的，第二就是使用pair類型。

Pair是庫中定義好的一個雙變量結構體，這里給出庫中pair的實現

template<class _Ty1,class _Ty2>
struct pair
{// store a pair of values
    typedef _Ty1 first_type;
    typedef _Ty2 second_type;
}

下面是Find函數的實現代碼：

typedef pair<Node*, int> FindType;
FindType Find(const K& key)
{
    Node* parent = NULL;
    Node* cur = _root;
    while(cur)
    {
        size_t i =0;
        while(i < cur->_size)
        {
            if(key > cur->_key[i])
            {
                i++;
            }
            else if(key < cur->_key[i])
            {
                break;
            }
            else
            {
                return FindType(cur, i);
            }
        }
        parent = cur;
        cur = cur->_sub[i];
    }
    return FindType(parent,-1);
}

第二步：插入算法 Insert()與分裂

    插入算法應該是比較復雜的了。

我們先考慮這樣一個問題，當插入一個元素之后（樹不為空樹），應該會有兩種情況，一種是該節點中關鍵字的個數并沒有超過或等于M，這個時候完全不需要調整，可以直接結束。另一種情況，也就是我們需要考慮的，當插入一個關鍵字之后，該節點的key滿了，這時候，就需要用到分裂算法。

我們來考慮，在下圖中的B樹中插入56，會發生哪些事。

    首先，我們應該先找到56應該插入的位置。這里Find()函數就可以幫得上忙。如果Find查找到了該key，就不需要再插入，如果沒有找到，返回最終找到空節點的父節點，直接在該節點中插入即可。在上圖中，用Find()函數查找56，返回的指針應該是指向右下角的結點，接下來開始插入節點。

        需要注意的是，這里把56插入之后，還做了件其他的事，57的左右孩子也跟著向右移動，因為它的左右孩子都是空結點，因此這里并沒有直接畫出來。

    接下來的任務就是開始分裂。

    對B樹的分裂，實際上是將關鍵字超出M-1的節點的中間關鍵字提取出來，同時將兩側分成兩個子節點。注意，這里只是把中間的關鍵字取出來，然后把中間的關鍵字再次插入到它的父節點中，同時將分裂產生的的新節點連接到父節點上。連接到父節點上的位置，與向父節點中插入新的關鍵字的位置有關，如圖：

    調整之后如果發現，父節點的關鍵字個數又超出了范圍，如上圖，則再向上分裂增長，直到某一次插入之后，關鍵字的個數不超過M-1，則停止分裂并返回，或者某次分裂到根節點之后，對根節點特殊處理，之后直接結束程序。這就是分裂算法。

   多注意一點的是，我們第二次插入的過程中，插入了key值，同時將分裂產生的節點也連接到了父節點上，因此，這里對插入key的過程做了一次封裝，實現如下：

void InsertKey(Node* node, const K& key, Node* sub)
{
    size_t index = node->_size-1;
    // 比key小的關鍵字連帶孩子節點同時向后移動
    while (index >= 0)
    {
        if (node->_key[index] > key)
        {
            //向后移動
            node->_key[index + 1] = node->_key[index];
            node->_sub[index + 2] = node->_sub[index + 1];
        }
        else // (node->_key[index] < key)
        {
            break;
        }
        --index;
    }
    // 將key插入到node結點當中
    node->_key[index + 1] = key;
    
    // 將分裂產生的結點連接在node節點上
    node->_sub[index + 2] = sub;
    if (sub != NULL)
    sub->_parent = node;
    
    // 對node的size調整
    node->_size++;
}

下面是插入節點實現代碼：

bool Insert(const K& key)
{
    // 樹是空樹
    if (_root == NULL)
    {
        _root = new Node;
        _root->_key[0] = key;
        _root->_parent = NULL;
        _root->_size = 1;
        return true;
    }
    // 在樹中Find該結點
    FindNode ret = Find(key);
    if (ret.second != -1) // 樹中找到該節點
        return false;
    Node* cur = ret.first;
    Node* parent = cur->_parent;
    Node* sub = NULL;
    int newkey = key;
    while (1)
    {
        //在 cur 節點里面插入key、sub
        //如果cur沒滿，跳出循環
        //cur->key滿了，向上分裂
        InsertKey(cur, newkey, sub);
        if (cur->_size < M)
            return true;

        //開始分裂
        size_t mid = cur->_size / 2;
        newkey = cur->_key[mid]; // 獲取下一次要插入的值
        Node* tmp = new Node;
        size_t j = 0;
        size_t i = 0;
        size_t sz = cur->_size;
        for (i = mid + 1; i < sz; i++)
        {
            tmp->_key[j] = cur->_key[i];
            tmp->_sub[j] = cur->_sub[i];
            //注意子節點的父指針
            if (tmp->_sub[j])
            tmp->_sub[j]->_parent = tmp;
            j++;
            tmp->_size++; // 調整size
            cur->_size--;
            cur->_key[i] = K(); // 將cur分裂出去的部分恢復默認值
            cur->_sub[i] = NULL;
        }
        tmp->_sub[j] = cur->_sub[i];
        //注意子節點的父指針
        if (tmp->_sub[j])
        tmp->_sub[j]->_parent = tmp;
        cur->_sub[i] = NULL;
        // 清空原來的key[mid]結點
        cur->_key[mid] = K();
        cur->_size--;
        //根節點
        if (parent == NULL)
        {
            _root = new Node;
            _root->_key[0] = newkey;
            _root->_size = 1;
            _root->_sub[0] = cur;
            _root->_sub[1] = tmp;
            cur->_parent = _root;
            tmp->_parent = _root;
            return true;
        }
        //非根節點
        cur = parent;
        parent = parent->_parent;
        sub = tmp;
    }
    return true;
}

    要實現插入算法，就是要通過分裂實現，通過判斷結點關鍵字的個數，決定是否分裂，分裂就是以中間的關鍵字為斷點，一分為二，提出中間關鍵字繼續向上插入。兩個分節點連接到上一層結點。

第三步：中序遍歷算法

    之所以要實現中序遍歷，是因為對于一棵平衡搜索樹而言，中序遍歷的結果是有序的，中序遍歷采用遞歸實現并不難，但要注意的一個問題是對每個key進行訪問的同時，我們不能再對兩個孩子進行遞歸訪問，因為這會對中間的孩子訪問兩次。如下圖：

    對中間的結點訪問了兩次，因此在普通二叉搜索樹上除了要增加對每個結點中key的訪問，也要禁止對左右子樹都遍歷，于是有如下實現代碼：

// 實現代碼 1
void _InOrder(Node* root)
{
    if (root == NULL)
        return;
    size_t i = 0;
    for (i = 0; i < root->_size; i++)
    {
        _InOrder(root->_sub[i]);
        cout << root->_key[i] << " ";
    }
    _InOrder(root->_sub[i]);
}

// 實現代碼 2
void _InOrder(Node* root)
{
    if (root == NULL)
        return;
    for (size_t i = 0; i < root->_size; i++)
    {
        _InOrder(root->_sub[i]);
        cout << root->_key[i] << " ";
        //遍歷過程中存在沖突，因為存在兩個指針指向一個結點的情況
        //解決方案：只打印前一半，到最后一個key的時候再打印后一半
        if (i == root->_size-1)
            _InOrder(root->_sub[i + 1]);
    }
}

    關于測試用例，最直接的就是直接插入1到20，經過測試，1~20 依次插入，包含了所有情況，如果中序遍歷可以有序輸出，那么表明B樹的實現基本已經可以滿足要求。

    B樹及B樹的變形，都是減少為了對磁盤的操作，上面看到當我們插入多個節點，它會進行多次的分裂，但當我們把M放到很大，那么它的高度就會成M的指數下降。

    當 M=1024 的時候，三層可以容納10億個結點，換句話說，10億結點我們只需要查找三次，對于每個節點中的key值，因為是有序的，采用二分查找不過10次，因此，在查找速度上是非常快的，也就減少了訪問磁盤的次數。

    對B樹的應用，主要都體現在B樹的變形上的應用，這也是大多數數據庫設計的底層實現。