数据结构与算法--B树（B-树）

Posted on Nov 4, 2019

1 引言

数据库的增删改查等操作是开发过程中最为常见也是尤为重要的，尤其是现在大数据的兴起，导致数据存储量急剧增加，提升数据的操作效率就变得尤为关键。大部分数据库的索引都采用树的结构存储，这是因为树的查询效率相对较高，且保持有序。
对于二叉搜索树的时间复杂度是O(logN)，在算法以及逻辑上来分析，二叉搜索树的查找速度以及数据比较次数都是较小的。但是我们不得不考虑一个新的问题。数据量是远大于内存大小的，那我们在查找数据时并不能将全部数据同时加载至内存。既然不能全部加载至内存中就只能逐步的去加载磁盘中某个页，简而言之就是逐一的去加载磁盘，加数据分块的加载至内存进行查找与比较。
例如：在图1.1所示的树中查找10，树中的每个节点代表一个磁盘页。每次访问一个新节点代表一次磁盘IO。

图1.1

图1.1

通过查找过程可以看出，磁盘IO次数与树的高度相关，在最坏情况下，磁盘IO次数等于树的高度。由于磁盘IO过程是相对耗时效率较低的，因此，在设计数据存储结构时需要降低树的高度，即将一棵“瘦高”的树变得“矮胖”。
当数据数目相同，在保持有序前提下，降低树高度，只需将节点中存储的key值增加，即二叉搜索树中每个节点只有一个key，现将一个节点中存储多个key，得到的树即为B树。

2 定义

B树也称B-树,B-树直接读作B树，不能因为有“-”号就读作B减树，它是一颗多路平衡查找树。我们描述一颗B树时需要指定它的阶数，阶数表示了一个结点最多有多少个孩子结点，一般用字母m表示阶数。当m取2时，就是我们常见的二叉搜索树，m为3时是2-3树。
一颗m阶的B树定义如下：

（1）每个结点最多有m-1个关键字。
（2）根结点最少可以只有1个关键字。
（3）非根结点至少有Math.ceil(m/2)-1个关键字。Math.ceil(m/2)含义是向上取整。例如Math.ceil(4.5) = 5。
（4）每个结点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它。
（5）所有叶子结点都位于同一层，或者说根结点到每个叶子结点的长度都相同。

3 查找

B-树的查找其实是对二叉搜索树查找的扩展，与二叉搜索树不同的地方是，B-树中每个节点有不止一棵子树。在B-树中查找某个结点时，需要先判断要查找的结点在哪棵子树上，然后在结点中逐个查找目标结点。B树的查找过程相对简单，与二叉搜索树类似，因此不再赘述。

4 插入

B树的插入操作是指在树种插入一条新记录，即（key, value）的键值对。如果B树中已存在需要插入的键值对，则用需要插入的value替换旧的value。若B树不存在这个key，则一定是在叶子结点中进行插入操作。

4.1 插入流程

B树的插入流程如下：
（1）根据要插入的key的值，对B树执行查找操作，查找到待插入数据的当前节点位置。
（2）判断当前结点key的个数是否小于等于m-1，若满足，则结束直接插入数据，否则，进行第（3）步。
（3）以结点中间的key为中心分裂成左右两部分，然后将这个中间的key插入到父结点中，这个key的左子树指向分裂后的左半部分，这个key的右子支指向分裂后的右半部分，然后将当前结点指向父结点，继续进行第（3）步。

4.2 实例图解

下面以5阶B树为例，介绍B树的插入操作，在5阶B树中，结点最多有4个key,最少有2个key。

插入图解：
1：插入38，此时为空树，直接插入，并作为根节点。继续插入22、76、40，符合情形（2），直接插入。继续插入51，符合情形（3），执行分裂。

2：按照相同的步骤继续插入13、21。插入39，符合情形（3），导致节点分裂。选择中值22作为父节点，并将22节点上移，与40节点进行合并。

3：按照同样的插入规则，继续向树中插入key为30、27、33、36、35、34、24、29的数据。插入完成后，继续插入key为26的数据，插入之后需要执行节点分裂。

4：将key为27的数据节点上移至父节点，此时父节点已经有4个key，插入key27的数据后需要执行节点分裂。在插入key为26的数据后，导致根节点发生分裂，树的高度加1。

4.3 性能分析

B树插入过程首先需要执行一次查找操作，B树的查找操作的时间复杂度为O(mlogmn)。其中m为B树的阶数，n为B树中key的数目。在插入过程，最耗时的情形即为：插入数据后导致根节点发生分裂，分裂节点的操作是常数级，分裂操作向上回溯的时间复杂度为O(h)。因此，B树的插入操作的时间复杂度近似于查找操作，即O(mlogmn)。

5 删除

5.1 删除流程

B树的删除流程如下：
（1）如果当前需要删除的key位于非叶子结点上，则用后继key（这里的后继key均指后继记录的意思）覆盖要删除的key，然后在后继key所在的子支中删除该后继key。此时后继key一定位于叶子结点上，这个过程和二叉搜索树删除结点的方式类似。删除这个记录后执行第2步
（2）该结点key个数大于等于Math.ceil(m/2)-1，结束删除操作，否则执行第（3）步。
（3）如果兄弟结点key个数大于Math.ceil(m/2)-1，则父结点中的key下移到该结点，兄弟结点中的一个key上移，删除操作结束。否则，将父结点中的key下移与当前结点及它的兄弟结点中的key合并，形成一个新的结点。原父结点中的key的两个孩子指针就变成了一个孩子指针，指向这个新结点。然后当前结点的指针指向父结点，重复第（2）步。

5.2 实例图解

删除图解：
1：首先删除21，符合情形（2）直接删除。删除21后，继续删除27，符合情形（1），使用后继节点28替代27，并删除28。

2：删除28后，当前节点只有一个key，因此需要按照情形（3）调整。当前节点的兄弟节点有3个key，父节点中key28下移，兄弟节点中key26上移，调整结束。调整完毕后继续删除32。

3：删除32后，需要按照情形（3）进行调整，当前节点的兄弟节点只有2个key，则将父节点下移，将当前节点与一个兄弟节点合并，调整完毕。继续删除39，删除39后按照情形（3）进行调整。

4：当前节点变为只含有key40的节点，需要按照情形（3）继续调整，执行节点的合并，合并操作中包含根节点，导致合并之后的树的高度减1。

5.3 性能分析

B树的删除操作同样需要执行查找过程，时间复杂度为O(mlogmn)。删除数据过程与插入过程类似，最坏情况需要回溯O(h)。因此B树的删除操作的时间复杂度近似为O(mlogmn)。

6 总结

B树是一种平衡的多路查找树。其设计思路主要是通过节点中存储不止一个key，来降低树的高度。同等比较次数下，树的高度小保证磁盘IO次数相对较少，提高查找效率。

7 代码实现

#include<iostream>
using namespace std;
 
//定义B树的节点结构
class BTreeNode
{
    int *keys;  //存储key的数组
    int t;      //允许存储的最多key数目，即阶数
    BTreeNode **C; //存储孩子数组指针
    int n;     //存储当前key的数目
    bool leaf; //判断此节点是否为叶子节点
 
public:
 
    BTreeNode(int _t, bool _leaf);   // 构造函数
 
    //遍历树
    void traverse();
 
    //查找键值为k的节点，若查找失败返回空
    BTreeNode *search(int k); 
 
    //查找键值为k的索引位置
    int findKey(int k);
 
    //插入
    void insertNonFull(int k);
 
    //分裂
    void splitChild(int i, BTreeNode *y);
 
    //删除键值为k的数据
    void remove(int k);
 
    //删除叶子节点
    void removeFromLeaf(int idx);
 
    //删除非叶子节点
    void removeFromNonLeaf(int idx);
 
    //获取前驱节点
    int getPred(int idx);
 
    //获取后继节点
    int getSucc(int idx);
 
    //填充节点
    void fill(int idx);
 
    //向父节点借用key
    void borrowFromPrev(int idx);
 
    // 从C[idx+1]-th节点借用一个key，并将其放在C[idx]第th节点中
    void borrowFromNext(int idx);
 
    //节点合并
    void merge(int idx);
 
    friend class BTree;
};

//定义树结构
class BTree
{
    BTreeNode *root; //根节点指针
    int t;  
public:
 
    // 构造函数
    BTree(int _t)
    {
        root = NULL;
        t = _t;
    }
 
	//遍历
    void traverse()
    {
        if (root != NULL) root->traverse();
    }
    //查找
    BTreeNode* search(int k)
    {
        return (root == NULL)? NULL : root->search(k);
    }
    //插入
    void insert(int k);
 
    //删除
    void remove(int k);
 
};

//构造函数
BTreeNode::BTreeNode(int t1, bool leaf1)
{
    //定义树的阶
    t = t1;
    leaf = leaf1;
 
    //根据树的阶数，分配数据空间
    keys = new int[2*t-1];
    C = new BTreeNode *[2*t];
    //当前key数目为0
    n = 0;
}
 
//查找键值为key的节点
int BTreeNode::findKey(int k)
{
    int idx=0;
    while (idx < n && keys[idx] < k)
        ++idx;
    return idx;
}
 
//删除键值为k节点
void BTreeNode::remove(int k)
{
	//首先执行查找过程
    int idx = findKey(k);
 
    //查找到节点
    if (idx < n && keys[idx] == k)
    {
        if (leaf)//如果是叶子节点，调用删除叶子节点的方法
            removeFromLeaf(idx);

        else //如果不是叶子节点，则调用非叶子节点的删除方法
            removeFromNonLeaf(idx);
    }
    else 
    {
 
        //如果查找结束位置为叶子节点，则查找失败
        if (leaf)
        {
            cout << "待删除的key =  "<< k <<"不存在\n";
            return;
        }
 
        //标记此节点，如果此节点位于
        bool flag = ( (idx==n)? true : false );
 
        //如果该键存在的子节点的t键更少，则填充该子节点
        if (C[idx]->n < t)
            fill(idx);
 
        //如果最后一个子节点已经合并，那么它必须与前一个子节点合并，
		//因此我们对(idx-1)第1个子节点进行递归。否则，我们递归到第(idx)个子节点上
        if (flag && idx > n)
            C[idx-1]->remove(k);
        else
            C[idx]->remove(k);
    }
    return;
}
 
//删除叶子节点
void BTreeNode::removeFromLeaf (int idx)
{
 
    //将idx-th之后的所有键向后移动一个位置
    for (int i=idx+1; i<n; ++i)
        keys[i-1] = keys[i];
 
    //减少key的数目
    n--;
 
    return;
}
 
//删除非叶子节点
void BTreeNode::removeFromNonLeaf(int idx)
{
 
    int k = keys[idx];
 
    //如果k (C[idx])之前的子元素至少有t个键，那么在位于C[idx]的子树中找到k的前驱节点
	//用前驱代替k。在递归删除前驱节点
    if (C[idx]->n >= t)
    {
        int pred = getPred(idx);
        keys[idx] = pred;
        C[idx]->remove(pred);
    }
 
    //如果子C[idx]的键值数目小于t，则检查C[idx+1]。如果C[idx+1]中至少有t个键，则查找k的后继节点
	//使用后继节点替换k，递归删除后继节点
    else if  (C[idx+1]->n >= t)
    {
        int succ = getSucc(idx);
        keys[idx] = succ;
        C[idx+1]->remove(succ);
    }
 
    // 如果C[idx]和C[idx+1]键值数目均少于t，则合并k和C[idx+1]至C[idx]
    // 合并后C[idx]包含2t-1个key，删除C[idx+1]，然后在C[idx]中递归删除后继节点
    else
    {
        merge(idx);
        C[idx]->remove(k);
    }
    return;
}
 
//获取前驱节点
int BTreeNode::getPred(int idx)
{
    //一直向最右子树移动，直到到达叶子节点
    BTreeNode *cur=C[idx];
    while (!cur->leaf)
        cur = cur->C[cur->n];
 
    //返回前驱节点
    return cur->keys[cur->n-1];
}
//获取后继节点
int BTreeNode::getSucc(int idx)
{
 
    //一直向最左的子树移动，直至到达叶子节点
    BTreeNode *cur = C[idx+1];
    while (!cur->leaf)
        cur = cur->C[0];
 
    //返回后继节点
    return cur->keys[0];
}
 
//一个用来填充子C[idx]的函数，它的键值小于t-1
void BTreeNode::fill(int idx)
{
 
    //如果前一个子节点(C[idx-1])具有多于t-1的键，则从该子节点借用一个键
    if (idx!=0 && C[idx-1]->n>=t)
        borrowFromPrev(idx);
 
    //如果下一个子节点(C[idx+1])的键数大于t-1，则从该子节点借用一个键
    else if (idx!=n && C[idx+1]->n>=t)
        borrowFromNext(idx);
 
    //如果C[idx]是最后一个子元素，则将它与前一个子元素合并，否则将它与下一个子元素合并
    else
    {
        if (idx != n)
            merge(idx);
        else
            merge(idx-1);
    }
    return;
}
 
//从前一个子节点(C[idx-1])借用一个键
void BTreeNode::borrowFromPrev(int idx)
{
 
    BTreeNode *child=C[idx];
    BTreeNode *sibling=C[idx-1];
 
    //C[idx-1]中的最后一个键向上到达父键，并将父键[idx-1]作为C[idx]中的第一个键插入。
    //将C[idx]中的所有键向前移动一步
    for (int i=child->n-1; i>=0; --i)
        child->keys[i+1] = child->keys[i];
 
    //如果C[idx]不是叶子节点，则将其所有子指针向前移动一步
    if (!child->leaf)
    {
        for(int i=child->n; i>=0; --i)
            child->C[i+1] = child->C[i];
    }
 
    //将子节点的第一个键设置为当前节点的键[idx-1]
    child->keys[0] = keys[idx-1];
 
    //将兄弟节点的最后一个孩子移动为C[idx]的第一个孩子
    if (!leaf)
        child->C[0] = sibling->C[sibling->n];
 
    //将键从同级键移到父级键，这会减少同级键的数量
    keys[idx-1] = sibling->keys[sibling->n-1];
 
    child->n += 1;
    sibling->n -= 1;
 
    return;
}
 
//从后继节点借用一个键
void BTreeNode::borrowFromNext(int idx)
{
 
    BTreeNode *child=C[idx];
    BTreeNode *sibling=C[idx+1];
 
    //键[idx]作为C[idx]中的最后一个键插入
    child->keys[(child->n)] = keys[idx];
 
	//将兄弟节点的第一个子元素作为最后一个子元素插入到C[idx]中
    if (!(child->leaf))
        child->C[(child->n)+1] = sibling->C[0];
 
    //将兄弟节点中的第一个键插入至[idx]
    keys[idx] = sibling->keys[0];
 
    //将兄弟节点中的所有键向后移动一步
    for (int i=1; i<sibling->n; ++i)
        sibling->keys[i-1] = sibling->keys[i];
 
    //将子指针向后移动一步
    if (!sibling->leaf)
    {
        for(int i=1; i<=sibling->n; ++i)
            sibling->C[i-1] = sibling->C[i];
    }
 
    child->n += 1;
    sibling->n -= 1;
 
    return;
}
 
//合并
void BTreeNode::merge(int idx)
{
    BTreeNode *child = C[idx];
    BTreeNode *sibling = C[idx+1];
 
    //从当前节点中取出出一个key，插入到C[idx]的(t-1)位置
    child->keys[t-1] = keys[idx];
 
    //将key从C[idx+1]复制到最后的C[idx]
    for (int i=0; i<sibling->n; ++i)
        child->keys[i+t] = sibling->keys[i];
 
    //将孩子指针从C[idx+1]复制到C[idx]
    if (!child->leaf)
    {
        for(int i=0; i<=sibling->n; ++i)
            child->C[i+t] = sibling->C[i];
    }
 
    //将当前节点中的所有键在idx之后移动一步，以填补将键[idx]移动到C[idx]所造成的空白。
    for (i = idx+1; i<n; ++i)
        keys[i-1] = keys[i];
 
    //将子指针移动到当前节点(idx+1)的后面
    for (i=idx+2; i<=n; ++i)
        C[i-1] = C[i];
 
    // 更新数据值
    child->n += sibling->n+1;
    n--;
 
    //删除兄弟节点
    delete(sibling);
    return;
}
 
//插入
void BTree::insert(int k)
{
    //树为空
    if (root == NULL)
    {
        //直接作为根节点插入
        root = new BTreeNode(t, true);
        root->keys[0] = k;  
        root->n = 1; 
    }
    else //树不为空
    {
        //判断树是否已满
        if (root->n == 2*t-1)
        {
            //树已满则重新创建根节点
            BTreeNode *s = new BTreeNode(t, false);
 
            //将原树根节点作为新树子节点
            s->C[0] = root;
 
            //分裂子节点
            s->splitChild(0, root);
 
            // 新的根节点有两个孩子
            int i = 0;
            if (s->keys[0] < k)
                i++;
            s->C[i]->insertNonFull(k);
 
            //改变根节点
            root = s;
        }
        else  //树不为空，插入k
            root->insertNonFull(k);
    }
}
 
//插入k
void BTreeNode::insertNonFull(int k)
{
    int i = n-1;
 
    // 插入位置为叶子节点
    if (leaf == true)
    {
        //查找要插入的新键的位置，将所有较大的键移动到前面的一个位置
        while (i >= 0 && keys[i] > k)
        {
            keys[i+1] = keys[i];
            i--;
        }
 
        //插入数据
        keys[i+1] = k;
        n = n+1;//更新key的数目
    }
    else //插入位置部位叶子节点
    {
        // 查找插入位置
        while (i >= 0 && keys[i] > k)
            i--;
 
        // 插入位置的节点是否已满
        if (C[i+1]->n == 2*t-1)
        {
            //如果已满，则执行分裂
            splitChild(i+1, C[i+1]);
 
            //分裂后在决定那个孩子插入此key
            if (keys[i+1] < k)
                i++;
        }
		//递归调用插入k
        C[i+1]->insertNonFull(k);
    }
}
 
//子节点分裂
void BTreeNode::splitChild(int i, BTreeNode *y)
{
    //创建新的父节点
    BTreeNode *z = new BTreeNode(y->t, y->leaf);
	//新节点的key数目为t-1
    z->n = t - 1;
 
    //将y中的后(t-1)key复制到z
    for (int j = 0; j < t-1; j++)
        z->keys[j] = y->keys[j+t];
 
    // Copy the last t children of y to z
    if (y->leaf == false)
    {
        for (j = 0; j < t; j++)
            z->C[j] = y->C[j+t];
    }
 
    //减少y中键的数量
    y->n = t - 1;
 
    //创建新子节点的空间
    for ( j = n; j >= i+1; j--)
        C[j+1] = C[j];
 
    // 将新子节点链接到此节点
    C[i+1] = z;
 
    //重新查找key位置
    for ( j = n-1; j >= i; j--)
        keys[j+1] = keys[j];
 
    // 将y的中间键值复制到此节点
    keys[i] = y->keys[t-1];
 
    // 增加节点数目
    n = n + 1;
}
 
//遍历树
void BTreeNode::traverse()
{
 
    int i;
    for (i = 0; i < n; i++)
    {
        if (leaf == false)
            C[i]->traverse();
        cout << " " << keys[i];
    }
    if (leaf == false)
        C[i]->traverse();
}
 
//查找
BTreeNode *BTreeNode::search(int k)
{
    // 找到第一个大于等于k的键
    int i = 0;
    while (i < n && k > keys[i])
        i++;
 
    // 查找成功
    if (keys[i] == k)
        return this;
 
    // 到达叶子节点，查找失败
    if (leaf == true)
        return NULL;
 
    // 递归
    return C[i]->search(k);
}

//删除
void BTree::remove(int k)
{
    if (!root)
    {
        cout << "The tree is empty\n";
        return;
    }
 
    root->remove(k);

    if (root->n==0)
    {
        BTreeNode *tmp = root;
        if (root->leaf)
            root = NULL;
        else
            root = root->C[0];
 
        //释放节点空间
        delete tmp;
    }
    return;
}
 
//测试程序
int main()
{
    BTree t(3); //创建阶为4的B树，最多允许有3个key
 
    t.insert(1);
    t.insert(3);
    t.insert(7);
    t.insert(10);
    t.insert(11);
    t.insert(13);
    t.insert(14);
    t.insert(17);
    t.insert(18);
    t.insert(16);
    t.insert(19);
    t.insert(24);
    t.insert(25);
    t.insert(29);
    t.insert(21);
    t.insert(4);
    t.insert(5);
    t.insert(20);
    t.insert(22);
    t.insert(2);
    t.insert(17);
    t.insert(12);
    t.insert(6);
 
    cout << "Traversal of tree constructed is\n";
    t.traverse();
    cout << endl;
 
    t.remove(6);
    cout << "Traversal of tree after removing 6\n";
    t.traverse();
    cout << endl;
 
    t.remove(13);
    cout << "Traversal of tree after removing 13\n";
    t.traverse();
    cout << endl;
 
    t.remove(7);
    cout << "Traversal of tree after removing 7\n";
    t.traverse();
    cout << endl;
 
    t.remove(4);
    cout << "Traversal of tree after removing 4\n";
    t.traverse();
    cout << endl;
 
    t.remove(2);
    cout << "Traversal of tree after removing 2\n";
    t.traverse();
    cout << endl;
 
    t.remove(16);
    cout << "Traversal of tree after removing 16\n";
    t.traverse();
    cout << endl;
 
    return 0;
}

树论和图论