B-Tree B-树 代码介绍-20230505（C语言)

1. 前言

前面已经介绍B-树属于多路查找树，它在数据库和文件储存系统设计中有着广泛的应用，B-Tree的基本操作包含查询、插入和删除等基本操作，由于这些操作过程中，B-树必须恪守其基本特性，尤其是结点中关键字数量的限制，导致在插入过程中产生“分裂”操作或在删除过程中需要“合并”结点。

本文着重探讨代码实现过程和思路，对于B-树的相关基本知识，大家可以参考相关书籍或上一篇文章关于B-树的介绍。

2. B-树操作实现

2.1 数据结构定义

如之前介绍，B-树的关键字插入或删除，可以采用自上而下或者自下而上中的任何策略。本文中描述的算法思路来自严蔚敏《数据结构》，采用的自下而上的程序结构，如有兴趣，也可参考《算法导论》中的自上而下的操作思路。

本文中涉及的无论删除还是插入操作，切入点都是B-树的最底层非叶子结点，由于要不断追寻上一层结点，所以数据结构中自然而然就需有双亲结点进行跟踪，根据树的定义，需要定义关键字数组和关键字信息指针，同时还需包括指向子树的指针。

数据结构定义：

#define m 3 //m 代表B-树的阶数


typedef int   KeyType;
typedef char* Record;


typedef struct  SElemType
{
    KeyType key;
    Record  value;
}SElemType;

typedef struct SSTable
{
    SElemType *elem;
    int        len;
} SSTable;


typedef struct BTNode
{
    int keynum; //number of keys in each node

    struct BTNode *parent; //parent node pointer

    KeyType   key[m+1]; //record in the node
    Record    recptr[m+1];//record pointer in the node

    struct BTNode *ptr[m+1]; //substree pointer

}BTNode, *BTree;

B-tree的搜索不断搜索关键字以及寻找指向子树指针的过程，这两个过程不断交替，直至到叶子结点结束位置，如果找到合适的关键字，那么就需要返回至少两个关键信息： 结点的指针和关键字在结点中所处位置，同时考虑查询失败的情况，需要一个标志位来指示查找是否成功。基于上述需求，我们定义搜索结果的返回对象的数据结构包含上述需求。

typedef struct Result
{
    BTNode *pt; //pointing to the target node
    int i;  // the index in each node[1....m];
    int tag; //1=found; 0=not found
}Result;

2.2 B-树查找操作实现

B-树查找需要在寻找结点与在结点中寻找交叉进行，它涉及到树的结点的查找，以及对结点中有序关键字的查找，对结点中的有序关键字，可以采用二叉查找树算法进行搜索；对于结点（指针）查找，可以选择迭代或递归方式进行。

• 迭代方式查找

#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
#define LQ(a,b) ((a)<=(b))


Result search_btree(BTree bt, KeyType key)
{
    int i;
    Result res;
    bool found=false;
    BTree p;
    BTree q;

    i=0;
    p=bt;
    q=NULL; //q is the parent of p

    while(!found && p)
    {
        i=search_index(p,key);

        if(EQ(key,p->key[i]))
        {
            found=true; //find the key successfully
        }
        else
        {
            q=p;
            p=p->ptr[i];
        }
    }

    if(found)
    {
        res.i=i;
        res.pt=p;
        res.tag=1;
    }
    else
    {
        res.i=i;
        res.pt=q;
        res.tag=0;
    }

    return res;
}


int search_index(BTree p, KeyType key)
{
    int low;
    int high;
    int mid;

    low=1;
    high=p->keynum;

    while(low<=high)
    {
        mid=(low+high)/2;

        if(EQ(key,p->key[mid])) //if found, returning the mid position
        {
            return mid;
        }
        else if(LT(key,p->key[mid]))
        {
            high=mid-1;
        }
        else
        {
            low=mid+1;
        }
    }

    // if not found, it will return high(high <low at this point)
    return high; 
    
}

采用递归方式，需要保留前面查询的结果，对于search_index函数可以与上面的迭代查找共用，函数体中需要保留前面查询的结点指针值和指针所在位置。

// p will start with NULL it will act as parent node of q node
Result search_btree_recursion(BTree q, BTree p, int index, KeyType key)
{
    
    if(q!=NULL)
    {
        index=search_index(q,key);
        if(index>0 && q->key[index]==key) //Recursion termination condition -2
        {
            Result res;

            res.i=index;
            res.pt=q;
            res.tag=1;

            return res;
        }
        else
        {
           return search_btree_recursion(q->ptr[index],q,index,key);
        }
    }
    else //Recursion termination condition-1
    {
        Result res;

        res.i = index;
        res.pt = p;
        res.tag = 0;


        return res;
    }
}

2. 3 B-树插入操作实现

插入操作过程比较复杂，需要先找到待插入结点所在结点指针，这个结点一定位于最底层非叶子节点上，和二叉树插入类似，结点的插入操作首先发生在最底层非叶子节点上，然后根据插入后的结点中关键字数量，决定是否产生“分裂”操作还是插入就此完成。

当插入结点中的关键字数量达到一定阈值后，它就会触发分裂操作，如果其双亲结点也同样达到阈值，那么就一直向上分裂直至满足要求位置，如果根节点满足分裂条件，那么B-tree 的深度就增加1，前面提到过，B-树深度增加（成长）的唯一途径就是根节点分裂。

分裂结点的实现算法具体来说，把一个结点（m,A[0],(K[1],A[1]),…,(K[m],A[m]))分裂为两个结点，此时可将这个满结点分裂为：

p=(m/2-1,A[0],(K[1],A[1]),…,(K[m/2-1],A[m/2-1]))

和

p’=(m-m/2,A[m/2],(K[m/2+1],A[m/2+1]),…,(K[m],A[m]))

而关键字K[m/2]和p’一起插入到p的双亲结点中去。具体代码实现中，采用memcpy原 结点中q中的右半部分数据赋值给新建结点，然后对此结点的各个特性进行初始化，新结点的父节点和p结点的父节点一致，含有关键字的数量为m-s。由于原结点分裂，原来结点关键字数量需要更新，关键字数量从m减少至m/2-1。

考虑到新建结点中的子树指针的父节点仍然为p，需要对父节点的连接进行更新，更新后的父节点指针为p’，这里当然需要判断前提条件，如果分裂的结点子树为叶子结点，叶子结点不包含任何有用的信息，其子树指针为空，自然而然就无需更新父节点的指针。

void split_node(BTree q, int s, BTree *ap)
{
    int i;
    BTree new_node;

    new_node=(BTree)malloc(sizeof(BTNode));

    memcpy(new_node->ptr,q->ptr+s,sizeof(BTNode *)*(m-s+1));
    memcpy(new_node->key+1, q->key + s + 1, sizeof(KeyType)*(m-s));
    memcpy(new_node->recptr+1, q->recptr + s + 1, sizeof(Record) * (m - s));

    new_node->keynum=m-s;
    q->keynum=s-1;
    *ap=new_node;
    (*ap)->parent=q->parent;

    //Build the parent link if the (*ap)->ptr[i] is not NULL
    for (i = 0; i <= (*ap)->keynum; i++)
    {
        if ((*ap)->ptr[i])
            (*ap)->ptr[i]->parent = *ap;
    }

    return;
}

如果需要在已有的节点上插入Key[i]和A[i]，需要对插入点之后的元素向右移动，然后空出指定的插入位置。最后进行赋值操作完成插入操作即可。函数中需要包含插入结点的指针，插入位置以及待插入关键值，待插入的子树指针。由于在分裂结点的创建已经对A[i]的父节点指针进行赋值，所以无需再对parent进行赋值操作。

具体的代码实现方式，

void insert_key(BTree q, int i, KeyType key, BTree ap)
{
    int k;

    for(k=q->keynum;k>i;k--)
    {
        q->ptr[k+1]=q->ptr[k];
        q->key[k+1]=q->key[k];
        q->recptr[k+1]=q->recptr[k];        
    }

    q->key[i+1]=key;
    q->ptr[i+1]=ap;
    q->recptr[i+1]=NULL;

   // if(ap)
    //{
        //ap->parent=q;
    //}

    q->keynum+=1;

    return;
}

上面提到了，在节点的插入过程中，可能会导致根节点分裂，根节点分裂需要建立根节点，同时对根节点进行重新赋值，所以我们需要涉及根节点分裂函数（创建函数）。

void create_new_root(BTree *bt, BTree q, KeyType x, BTree ap)
{
    BTree new_node;

    new_node=(BTree)malloc(sizeof(BTNode));

    new_node->ptr[0]=(*bt);
    new_node->key[1]=x;
    new_node->recptr[1]=NULL;
    new_node->ptr[1]=ap;
    new_node->parent=NULL;
    new_node->keynum=1;

    if(*bt)
    {
        (*bt)->parent = new_node;
    }

    if(ap)
    {
        ap->parent = new_node;
    }
   

    (*bt)=new_node;

    return;
}

最后我们来到节点插入函数，有了上述铺垫之后，节点插入函数实现就是水到渠成的事情了。过程中我们需要跟踪插入是否完成，如果插入后，结点中的关键字数量小于m,则插入完成；如果插入未完成，则需要不断向上迭代，不断搜索新的关键值和指针在上一级结点中插入的位置。

如果bt是空树或者根节点已经已经分裂为结点*q 和 *ap ，那么就需要调用根节点生成函数，重新建立新的根节点。

void insert_btree(BTree *bt, KeyType key, BTree q, int i)
{
    int         s;
    BTree       ap=NULL; //application pointer;
    KeyType     x;

    bool        finished=false;

    x=key;

    while(q && !finished)
    {
        insert_key(q,i,x,ap);

        if(q->keynum < m)
        {
            finished=true;
        }
        else
        {
            s=(m+2-1)/2;
            x=q->key[s];
            split_node(q,s,&ap);
            q=q->parent;
            
            if(q)
            {
                i = search_index(q, x);
            }

        }
    }

    if (!finished)
    {
        create_new_root(bt, q, x, ap); // create_new_root(BTree *bt, BTree q,KeyType x,BTree ap);
    }

    return;
}

2.4 B-树删除操作

删除操作是B-树中最复杂，最难实现的功能，它涉及到多种情况的判断，以及条件判断或可能产生的递归调用，代码实现过程中参考了《数据结构-C语言版》（严蔚敏,吴伟民版）课本源码+习题集解析使用说明 - 康建伟 - 博客园 (cnblogs.com)中的代码，并进行微小更改，在此表示感谢。

按照实际应用，B-树的删除分为三类情况，但由于涉及到相邻的两个子树，程序中会涉及到更多的判断情况。删除过程的出发点是最底层的非终端结点，如果待删除对象位于中间结点中，在执行删除操作之前，可以用它的直接后继节点进行替换后，再进行相关的删除。子函数实现分别为：

2.4.1 查找直接后继关键字

某个结点的后继，其实就是其相邻有节点所指向的子树上的最小值，对其子树为参数，寻找关键字的后继。实现代码相对比较简单，不断在p->ptr[0]中进行迭代，直至为空，并且把位置i赋值为1.

Result find_successor(BTree bt)
{
    Result res;
    BTree p;

    p=bt;

    while(p->ptr[0]!=NULL)
    {
        p=p->ptr[0];
    }

    res.pt=p;
    res.i=1;
    res.tag=1;

    return res;
}

如果待删除对象位于中间结点中，删除前需要做替换处理，函数实现如下：

void delete_btree(BTree *bt, KeyType key)
{
    int i;
    Result res;
    Result successor;
    BTree p;
    BTree q;
    
    res=search_btree(*bt,key);
    q=res.pt->ptr[res.i];

    if(q!=NULL)
    {
        successor = find_successor(q);
        res.pt->key[res.i]=successor.pt->key[successor.i];
        res.pt->recptr[res.i]=successor.pt->recptr[successor.i];
        res=successor;
    }

    delete_key(bt,res.pt,res.i);
    
    return;
}

最后让我们看一下大名鼎鼎的删除操作具体函数的实现，这个函数过程中，如果待删除对象，相邻左右子树的关键字数量都为[m/2]-1，那么就需要在这个过程中，就需要进行递归前虚拟一个关键字，然后进行递归操作。具体实现方式，请读者自行理解。

void delete_key(BTree *bt, BTree q, int i)
{
    int s; //seperate point
    int flag;
    int order;
    int j;

    BTree p;
    BTree rc;
    BTree lc;

    s=(m+2-1)/2;

    flag=0;
    order=-1;
    p=NULL;

    if(!find_parent(q,&p,&order))
    {
        flag=1; //only root node
    }
    else
    {
        if(q->keynum>=s)
        {
            flag=2; //remove the key directly
        }
        else
        {
            if (flag == 0 && order < p->keynum && p->ptr[order + 1]->keynum >= s)
                flag = 3; // 右兄弟关键字个数>=┌M/2┐

            if (flag == 0 && order > 0 && p->ptr[order - 1]->keynum >= s)
                flag = 4; // 左兄弟关键字个数>=┌M/2┐

            if (flag == 0 && order < p->keynum && p->ptr[order + 1]->keynum == (s - 1))
                flag = 5; // 右兄弟关键字个数==┌M/2┐-1

            if (flag == 0 && order > 0 && p->ptr[order - 1]->keynum == (s - 1))
                flag = 6; // 左兄弟关键字个数==┌M/2┐-1
        }
    }


   switch (flag)
   {
   case 1:
        if(q->keynum==1 && i==1)
        {
            *bt=q->ptr[0]; //*bt==NULL;
        }
        else
        {
            memcpy(q->key + i, q->key + i+1,sizeof(KeyType)*(q->keynum-i));
            memcpy(q->recptr + i, q->recptr + i + 1, sizeof(Record) * (q->keynum - i));
            memcpy(q->ptr + i, q->ptr + i + 1, sizeof(BTNode *) * (q->keynum - i));
            q->keynum=q->keynum-1;
        }
    break;

   case 2:
            memcpy(q->key + i, q->key + i + 1, sizeof(KeyType) * (q->keynum - i));
            memcpy(q->recptr + i, q->recptr + i + 1, sizeof(Record) * (q->keynum - i));
            memcpy(q->ptr + i, q->ptr + i + 1, sizeof(BTNode *) * (q->keynum - i));
            q->keynum = q->keynum - 1;
    break;
   case 3: //右兄弟关键字个数>=┌M/2┐
            rc = p->ptr[order + 1];
            memcpy(q->key + i, q->key + i + 1, sizeof(KeyType) * (q->keynum - i));
            memcpy(q->recptr + i, q->recptr + i + 1, sizeof(Record) * (q->keynum - i));
            memcpy(q->ptr + i, q->ptr + i + 1, sizeof(BTNode *) * (q->keynum - i));

            q->key[q->keynum]=p->key[order+1];
            q->recptr[q->keynum]=p->recptr[order+1];
            q->ptr[q->keynum]=rc->ptr[0];

            

            p->key[order+1]=rc->key[1];
            p->recptr[order+1]=rc->recptr[1];
            rc->ptr[0]=rc->ptr[1];

            memcpy(rc->key + 1, rc->key + 2, sizeof(KeyType) * (rc->keynum - 1));
            memcpy(rc->recptr + 1, rc->recptr + 2, sizeof(Record) * (rc->keynum - 1));
            memcpy(rc->ptr + 1, rc->ptr + 2, sizeof(BTNode *) * (rc->keynum - 1));
            rc->keynum = rc->keynum - 1;

            break;
   case 4: // 左兄弟关键字个数>=┌M/2┐
            lc = p->ptr[order - 1];

            for(j=i;j>=2;j--)
            {
                q->key[j]=q->key[j-1];
                q->ptr[j]=q->ptr[j-1];
                q->recptr[j]=q->recptr[j-1];
            }

            q->ptr[1]=q->ptr[0];
            q->key[1]=p->key[order];
            q->ptr[0]=lc->ptr[lc->keynum];
            p->key[order]=lc->key[lc->keynum];       
            lc->keynum--;
            break;
   case 5: // 右兄弟关键字个数==┌M/2┐-1
            rc=p->ptr[order+1];

            memcpy(q->key + i, q->key + i + 1, sizeof(KeyType) * (q->keynum - i));
            memcpy(q->recptr + i, q->recptr + i + 1, sizeof(Record) * (q->keynum - i));
            memcpy(q->ptr + i, q->ptr + i + 1, sizeof(BTNode *) * (q->keynum - i));

            q->key[q->keynum] = p->key[order + 1];
            q->recptr[q->keynum]=p->recptr[order+1];
            q->ptr[q->keynum] = rc->ptr[0];

            memcpy(q->key + q->keynum+1, rc->key+1, sizeof(KeyType) * (rc->keynum));
            memcpy(q->recptr + q->keynum + 1, q->recptr + 1, sizeof(Record) * (rc->keynum));
            memcpy(q->ptr + q->keynum + 1, q->ptr + 1, sizeof(BTNode *) * (rc->keynum));

            q->keynum += rc->keynum;

            memcpy(p->key + order + 1, p->key + order + 2, sizeof(KeyType) * (p->keynum-order-1));
            memcpy(p->recptr + order + 1, p->recptr + order + 2, sizeof(Record) * (p->keynum - order - 1));
            memcpy(p->ptr + order + 1, p->ptr + order + 2, sizeof(BTNode *) * (p->keynum - order - 1));

            p->keynum--;

            if (p->keynum < (s - 1))
            {
                p->keynum++; // 构造一个虚拟关键字
                q = p;
                delete_key(bt, q, q->keynum);
            }

            break;
   case 6: // 左兄弟关键字个数==┌M/2┐-1
            lc = p->ptr[order - 1];
            lc->key[lc->keynum + 1] = p->key[order];
            lc->recptr[lc->keynum + 1] = p->recptr[order];
            lc->ptr[lc->keynum + 1] = q->ptr[0];

            memcpy(lc->key + lc->keynum + 2, q->key+1, sizeof(KeyType) * (i-1));
            memcpy(lc->recptr + lc->keynum + 2, q->recptr + 1, sizeof(Record) * (i - 1));
            memcpy(lc->ptr + lc->keynum + 2, q->ptr + 1, sizeof(BTNode *) * (i - 1));

            memcpy(lc->key + lc->keynum + i + 1, q->key + i + 1, sizeof(KeyType) * (q->keynum - i));
            memcpy(lc->recptr + lc->keynum + i + 1, q->recptr + i + 1, sizeof(Record) * (q->keynum - i));
            memcpy(lc->ptr + lc->keynum + i + 1, q->ptr + i + 1, sizeof(BTNode *) * (q->keynum - i));

            lc->keynum += q->keynum;

            memcpy(p->key + order , p->key + order + 1, sizeof(KeyType) * (p->keynum - order));
            memcpy(p->recptr + order, p->recptr + order + 1, sizeof(Record) * (p->keynum - order));
            memcpy(p->ptr + order, p->ptr + order + 1, sizeof(BTNode *) * (p->keynum - order));

            p->keynum--;
            if (p->keynum < (s - 1))
            {
                p->keynum++; // 构造一个虚拟关键字
                q = p;
                delete_key(bt, q, q->keynum);
            }

            break;
   }
    

}

3. 小结

通过代码回顾，更好认识到B-树操作实现的复杂性，尤其是对关键字的删除操作的函数实现，更是分为多种情况进行讨论，对于删除函数中，进行单边标记的编程技巧的学习，也是受益匪浅。

参考资料：

《数据结构-C语言版》（严蔚敏,吴伟民版）课本源码+习题集解析使用说明 - 康建伟 - 博客园 (cnblogs.com)