C/C++Linux服务器开发 一、磁盘存储链式的B树与B+树

在前一篇博客中我们分析了“随处可见的红黑树”，相信大家都有了一定的了解。想了解的朋友可以去上面瞅瞅呢。而今天我们就要介绍适合磁盘存储的B树。b树的介绍、以及性质网上有很多，不是很了解得可以先找找，要知道B树的阶以及度，以及子树的性质，这里我们只对设计有个介绍。

1.B树的定义

多叉树等于B树，一颗M阶B树T，满足以下条件：
1 每个结点至少拥有M颗子树
2 根结点至少有两颗子树。
3 除根结点外，其余的每个分支结点至少拥有M/2颗子树。
4 所有叶子结点都在同一层==》保证平衡树
5 有k课子树的分支结点，则存在k-1个关键字，关键字按照递增进行排序。
6 关键字数量满足 ceil(M/2) -1 <= n <= M-1
实现设计时候
//度：t
//阶：2t
//结点最大元素: 2t-1

不了解度和阶的要先理解清楚，以及子树关系个数

2.B树的数据结构

typedef int KEY_TYPE;

//根据b树的性质进行定义
typedef struct _btree_node{
    struct _btree_node **children;//子树
    KEY_TYPE *keys;       //定义指针用于存储key

    int num;    //判断key的数量
    int leaf;   //用来判断当前节点是否是叶子节点 1：yes，0：no


}btree_node;

typedef struct _btree{
    btree_node * root;
    int t; //表示度：一个结点含有的子节点的个数

}btree;

3.创建结点

//创建节点
struct btree_node *btree_create_node(int t,int leaf)
{
    btree_node *node = (btree_node *)calloc(1,sizeof( btree_node));
    if(node == NULL){
        return NULL;
    }
    node->num = 0;
    node->keys = (KEY_TYPE *)calloc(1,(2 * t -1)*sizeof(KEY_TYPE)); //最多的key内存
    node->children = (btree_node **)calloc(1,2 * t *sizeof(btree_node *));//的子节点内存
    node->leaf = leaf;

    return node;

}

 4.销毁结点

//销毁节点
void btree_destroy_node( btree_node *node)
{
    if(node)
    {
        if(node->keys)
        {
            free(node->keys);
        }
        if(node->children)
        {
            free(node->children);
        }
        free(node);
    }
}

5.b树的创建

//b树的创建
void btree_create(btree *T,int t)
{
    T->t = t;
    struct btree_node *x = btree_create_node(t,1);//1为是根节点，0不是
    T->root = x;
}

6.b树的插入

//b树的插入
void btree_insert(btree *T,KEY_TYPE key)
{
     btree_node *root = T->root;
    if(root->num == 2 * T->t -1) //根结点的数量满了
    {
        btree_node *node = btree_create_node(T->t,0);
        T->root = node;

        node->children[0]  = root;
        btree_split_child(T,node,0);//分裂
    }else{
        btree_insert_nofull(T,root,key);//直接插入
    }
}

将b树的插入代码贴出来，然后我们分析下插入的流程如下所示

 我们需要添加L，我们是想将L加在最后面位置，我们先要判断结点数量是否满了，就是代码上的

if(root->num == 2 * T->t -1)，因为我们需要满足B树定义的性质，这个B树的度是3，所以最少的key数量为2，最多可以为5，而GHIJK已经五个，现在添加了L后明显超出key最大数量，此时我们需要分裂它  

7.B树的分裂（根结点满了）

还是以上图为例子，我们先定义一个空结点Z，将JK放入进去，将I上移到CF后面，再将Z放入到I的children中，如下代码实现分为1,2,3三个步骤。

//b树的分裂
void btree_split_child(btree *T,btree_node *x,int i)
{
    btree_node *y = x->children[i];
    btree_node *z = btree_create_node(T->t,y->leaf);


    //1.将J和K放入到Z结点中
    int j = 0;
    for(j = 0; j < T->t -1;j++)
    {
        z->keys[j] = y->keys[j+T->t];
    }
    if(y->leaf == 0)
    {
        for(j = 0;j < T->t;j++){
            z->children[j] = y->children[j + T->t];
        }
    }

    //2.将Y的key数量减1
    y->num = T->t - 1;

    //3.将y放入x中
    for(j = x->num;j>= i+1;j--)
    {
        x->children[j+1] = x->children[j];
    }
    x->children[i+1] = z;

    for(j = x->num -1;j>=i ;j--)
    {
        x->keys[j+1] = x->keys[j];
    }
    x->keys[i] = y->keys[T->t -1];
    x->num += 1;

}

以上是根结点满的情况下的使用，如果根结点不满呢直接使用btree_insert_nofull(T,root,key);//直接插入

8.根结点不满

//插入不满的结点
void btree_insert_nofull(btree *T,btree_node *x,KEY_TYPE key)
{
    int i = x->num - 1;
    if(x->leaf) //如果是叶子节点
    {
        while (i >= 0 && x->keys[i] > key) {
            x->keys[i +1] =  x->keys[i] ;
            i--;
        }
        x->keys[i + 1]  = key;
        x->num += 1;

    }else{//如果不是叶子节点
        while(i >= 0 && x->keys[i] >key) i--;
        if(x->children[i + 1]->num == 2*T->t-1)
        {
            btree_split_child(T,x,i);
            if(key > x->keys[i+1]) i++;
        }
        btree_insert_nofull(T,x->children[i+1],key);
    }
}

根结点不满的时候，我们又得考虑两种情况，1.如果我们插入的刚好是叶子节点，此时我们不用考虑子节点，直接将值插入进来，2.如果不是叶子节点，我们需要判断孩子节点是否满了，如果满了，继续分裂，之后我们再递归查询。至此插入分裂结束了。

结点的删除涉及到借位，合并，在下才疏学浅，只能简单介绍下

 至于删除合并的部分没有研究明白，等后面有时间了再来继续，但这里可以提供一份完全可用的插入、删除的B树代码。

代码链接:c/c++Linux服务器开发B树的建立-C/C++文档类资源-CSDN下载