算法导论 之 B-树(B树) - 创建 插入[C语言]

2022-06-23 03:57:47

1 引言


  In computer science, a B-tree is a tree data structure that keeps data sorted and allows searches, sequential access, insertions, and deletions in logarithmic time. The B-tree is a generalization of a binary search tree in that a node can have more than two children (Comer 1979, p. 123). Unlike self-balancing binary search trees, the B-tree is optimized for systems that read and write large blocks of data. It is commonly used in databases and filesystems.


  在计算机科学中，B树在查找、访问、插入、删除操作上时间复杂度为O（log2~n）（2为底数 n为对数），不像自平衡二叉查找树，其可以有效的优化系统对大块的数据读写的性能，其通常在数据库和文件系统中被使用。

  一棵m阶的B树，或为空树，或为满足下列特征的m叉树：

    ①、树中每个结点至多有m棵子树；

    ②、若根结点不是终端结点，则至少有2棵子树；

    ③、除根之外，所有非终端结点至少有算法导论 之 B-树(B树) - 创建 插入[C语言]棵子树；

    ④、所有的非终端结点中包含下列信息数据:

[n, C0, K0, C1, K1, C2, K2, ...., Kn-1, Cn]

        其中：Ki[i=0,1，...，n-1]为关键字，且Ki<Ki+1[i=0, 1, ..., n-2]；Ci[i=0,1,...,n]为至上子树根结点的指针，且指针Ci所指子树中所有结点的关键字均小于Ki[i=0,1,...,n-1]，但都大于Ki-1[i=1,...,n-1]；


2 编码实现


2.1 结构定义


  根据m阶B树的性质，B树的相关结构定义如下：

/* B树结点结构 */
typedef struct _btree_node_t
{
    int num;                        /* 关键字个数 */
    int *key;                       /* 关键字：所占空间为(max+1) */
    struct _btree_node_t **child;   /* 子结点：所占空间为（max+2） */
    struct _btree_node_t *parent;   /* 父结点 */
}btree_node_t;

代码1 结点结构

/* B树结构 */
typedef struct
{
    int max;                        /* 单个结点最大关键字个数 - 也就是max阶 */
    int min;                        /* 单个结点最小关键字个数 */
    btree_node_t *root;             /* B树根结点地址 */
}btree_t;

代码2 B树结构


2.2 创建B树


  此过程主要是完成btree_t中基本信息的设置，为后续处理创造条件。

/******************************************************************************
 **函数名称: btree_creat
 **功    能: 创建B树
 **输入参数: 
 **     _btree: B树
 **     max: 阶-单个结点的最大关键字个数(注：参数max的值不能小于2)
 **输出参数: NONE
 **返    回: 0:成功 -1:失败
 **实现描述: 
 **注意事项: 
 **     注意：参数max的值不能小于2.
 **作    者: # Qifeng.zou # 2014.03.12 #
 ******************************************************************************/
int btree_creat(btree_t **_btree, int max)
{
    btree_t *btree = NULL;

    if(max < 2)
    {
        fprintf(stderr, "[%s][%d] Parameter ‘max‘ must geater than 2.\n", __FILE__, __LINE__);
        return -1;
    }

    btree = (btree_t *)calloc(1, sizeof(btree_t));
    if(NULL == btree)
    {
        fprintf(stderr, "[%s][%d] errmsg:[%d] %s!\n", __FILE__, __LINE__, errno, strerror(errno));
        return -1;
    }

    btree->max= max;
    btree->min = max/2;
    if(0 != max%2)
    {
        btree->min++;
    }
    btree->min--;
    btree->root = NULL;

    *_btree = btree;
    return 0;
}
代码3 创建B树

2.3 插入操作


  B树是从空树起，逐个插入关键字而建立起来的，但由于B树结点中的关键字个数必须>=算法导论 之 B-树(B树) - 创建 插入[C语言]，因此，每次插入一个关键字不是在树中添加一个终端结点，而是首先在最底层的某个非终端结点中插入一个关键字，若该结点的关键字个数不超过m-1，则插入完成，否则要产生结点的“分裂”。假设现在需要构建一棵3阶B树，其插入操作的过程如下图所示：
  ① 插入关键字45
    刚开始为空树，因此插入成功后只有一个结点。
算法导论 之 B-树(B树) - 创建 插入[C语言]
图1 插入结点

  ② 插入关键字24和53
    在图1的基础上，插入关键字24和53后，该结点关键字个数num仍未超过max，因此不会进行“分裂”处理。插入完成后，该结点关键字个数num=3已经达到临界值max。
算法导论 之 B-树(B树) - 创建 插入[C语言]
图2 插入结点

  ③ 插入关键字90
    在图2基础上，插入关键字90后，该结点关键字个数num=4超过max值，需要进行“分裂”处理。
算法导论 之 B-树(B树) - 创建 插入[C语言]
图3 分裂处理

    当结点关键字个数num达到max时，则需要进行“分裂”处理，分割序号为num/2。图3中的[4| 24, 45, 53, 90]的分割序号为num/2 = 4/2 = 2，序号从0开始计数，因此关键字53为分割点，分裂过程如下：

    1）以序列号idx=num/2为分割点，原结点分裂为2个结点A[2| 24, 45]和B[1| 90]；

    2）原结点无父结点，则新建一个结点P，并将关键字插入到新结点P中；

    3）将结点A和B作为结点P的子结点，并遵循B树特征④；

    4）因结点P的结点数未超过max，则分裂结束。

  ④ 插入关键字46和47

    在图3右图的基础上，插入关键字46和47后，得到图4左图，此时结点[4| 24, 45, 46, 47]已经达到分裂条件。

算法导论 之 B-树(B树) - 创建 插入[C语言]

图4 分裂处理

    连续插入关键字46、47后，该结点[2| 24, 45]变为[4| 24, 45, 46, 47]，因此其达到了“分裂”的条件，其分裂流程如下：

    1）以序列号idx=num/2为分割点，结点[2| 24, 45, 46, 47]分裂为两个结点A[2| 24, 45]和B[1| 47]；

    2）分割点关键字46被插入到父结点P中，得到结点P[2| 46, 53]

    3）新结点B[1| 47]加入到结点P[2| 46, 53]的子结点序列中 - 遵循特征④

    4）因结点P[2| 46, 53]的关键字个数num为超过max，因为分裂结束。

  ⑤ 插入关键字15和18

    在图4右图的基础上，插入关键字15和18后，得到图5左图，此时结点[4| 15, 18, 24, 45]已经达到分裂条件。其处理过程同④，在此不再赘述。

算法导论 之 B-树(B树) - 创建 插入[C语言]

图5 分裂处理

  ⑥、插入关键字48、49、50

    在图5右图的基础上插入48、49、50，可得到图6左图，此时结点[1| 47, 48, 49, 50]已达到分裂条件。

算法导论 之 B-树(B树) - 创建 插入[C语言]

图6 分裂处理

    完成第一步分裂处理之后，父结点P[4| 24, 46, 49, 53]此时也达到了分裂条件。

算法导论 之 B-树(B树) - 创建 插入[C语言]

图7 进一步分裂

  综合①~⑥的插入操作过程，因此可以实现：

/******************************************************************************
 **函数名称: btree_insert
 **功    能: 插入关键字（对外接口）
 **输入参数: 
 **     btree: B树
 **     key: 被插入的关键字
 **输出参数: NONE
 **返    回: 0:成功 -1:失败
 **实现描述: 
 **注意事项: 
 **作    者: # Qifeng.zou # 2014.03.12 #
 ******************************************************************************/
int btree_insert(btree_t *btree, int key)
{
    int idx = 0;
    btree_node_t *node = btree->root;

    /* 1. 构建第一个结点 */
    if(NULL == node)
    {
        node = btree_creat_node(btree);
        if(NULL == node)
        {
            fprintf(stderr, "[%s][%d] Create node failed!\n", __FILE__, __LINE__);
            return -1;
        }

        node->num = 1; 
        node->key[0] = key;
        node->parent = NULL;

        btree->root = node;
        return 0;
    }

    /* 2. 查找插入位置：在此当然也可以采用二分查找算法，有兴趣的可以自己去优化 */
    while(NULL != node)
    {
        for(idx=0; idx<node->num; idx++)
        {
            if(key == node->key[idx])
            {
                fprintf(stderr, "[%s][%d] The node is exist!\n", __FILE__, __LINE__);
                return 0;
            }
            else if(key < node->key[idx])
            {
                break;
            }
        }

        if(NULL != node->child[idx])
        {
            node = node->child[idx];
        }
        else
        {
            break;
        }
    }

    /* 3. 执行插入操作 */
    return _btree_insert(btree, node, key, idx);
}
代码4 插入关键字（对外接口）
/******************************************************************************
 **函数名称: _btree_insert
 **功    能: 插入关键字到指定结点
 **输入参数: 
 **     btree: B树
 **     node: 指定结点
 **     key: 被插入的关键字
 **     idx: 指定位置
 **输出参数: NONE
 **返    回: 0:成功 -1:失败
 **实现描述: 
 **注意事项: 
 **作    者: # Qifeng.zou # 2014.03.12 #
 ******************************************************************************/
static int _btree_insert(btree_t *btree, btree_node_t *node, int key, int idx)
{
    int i = 0;

    /* 1. 移动关键字 */
    for(i=node->num; i>idx; i--)
    {
        node->key[i] = node->key[i-1];
    }

    node->key[idx] = key; /* 插入 */
    node->num++;

    /* 2. 分裂处理 */
    if(node->num > btree->max)
    {
        return btree_split(btree, node);
    }

    return 0;
}
代码5 插入结点

/******************************************************************************
 **函数名称: btree_split
 **功    能: 结点分裂处理
 **输入参数: 
 **     btree: B树
 **     node: 需要被分裂处理的结点
 **输出参数: NONE
 **返    回: 0:成功 -1:失败
 **实现描述: 
 **注意事项: 
 **作    者: # Qifeng.zou # 2014.03.12 #
 ******************************************************************************/
static int btree_split(btree_t *btree, btree_node_t *node)
{
    int idx = 0, i = 0, total = 0;
    btree_node_t *parent = NULL, *node2 = NULL;


    while(node->num > btree->max)
    {
        /* 分裂指定结点node */
        total = node->num;
        idx = (total >> 1); /* Split index */

        node2 = btree_creat_node(btree);
        if(NULL == node2)
        {
            fprintf(stderr, "[%s][%d] Create node failed!\n", __FILE__, __LINE__);
            return -1;
        }

        /* 数据拷贝 */
        memcpy(node2->key, node->key+idx+1, (total-idx-1) * sizeof(int));
        memcpy(node2->child, node->child+idx+1, (total-idx) * sizeof(btree_node_t *));

        node2->num = (total - idx - 1);
        node2->parent  = node->parent;

        node->num = idx;

        /* 分割关键字插入父结点 */
        parent  = node->parent;
        if(NULL == parent)
        {
            /* Split root node */
            parent = btree_creat_node(btree);
            if(NULL == parent)
            {
                fprintf(stderr, "[%s][%d] Create root failed!", __FILE__, __LINE__);
                return -1;
            }

            btree->root = parent;
            parent->child[0] = node;
            node->parent = parent;
            node2->parent = parent;

            parent->key[0] = node->key[idx];
            parent->child[1] = node2;
            parent->num++;
        }
        else
        {
            /* Insert into parent node */
            for(i=parent->num; i>0; i--)
            {
                if(node->key[idx] < parent->key[i-1])
                {
                    parent->key[i] = parent->key[i-1];
                    parent->child[i+1] = parent->child[i];
                }
                else
                {
                    parent->key[i] = node->key[idx];
                    parent->child[i+1] = node2;
                    node2->parent = parent;
                    parent->num++;
                    break;
                }
            }

            if(0 == i)
            {
                parent->key[0] = node->key[idx];
                parent->child[1] = node2;
                node2->parent = parent;
                parent->num++;               
            }
        }

        memset(node->key+idx, 0, (total - idx) * sizeof(int));
        memset(node->child+idx+1, 0, (total - idx) * sizeof(btree_node_t *));

        /* Change node2‘s child->parent */
        for(idx=0; idx<=node2->num; idx++)
        {
            if(NULL != node2->child[idx])
            {
                node2->child[idx]->parent = node2;
            }
        }
        node = parent;
    }

    return 0;
}
代码6 分裂处理
 
/******************************************************************************
 **函数名称: btree_creat_node
 **功    能: 新建结点
 **输入参数: 
 **     btree: B树
 **输出参数: NONE
 **返    回: 节点地址
 **实现描述: 
 **注意事项: 
 **作    者: # Qifeng.zou # 2014.03.12 #
 ******************************************************************************/
static btree_node_t *btree_creat_node(btree_t *btree)
{
    btree_node_t *node = NULL;


    node = (btree_node_t *)calloc(1, sizeof(btree_node_t));
    if(NULL == node)
    {
        fprintf(stderr, "[%s][%d] errmsg:[%d] %s\n", __FILE__, __LINE__, errno, strerror(errno));
        return NULL;
    }

    node->num = 0;

    /* More than (max) is for move */
    node->key = (int *)calloc(btree->max+1, sizeof(int));
    if(NULL == node->key)
    {
        free(node), node=NULL;
        fprintf(stderr, "[%s][%d] errmsg:[%d] %s\n", __FILE__, __LINE__, errno, strerror(errno));
        return NULL;
    }

    /* More than (max+1) is for move */
    node->child = (btree_node_t **)calloc(btree->max+2, sizeof(btree_node_t *));
    if(NULL == node->child)
    {
        free(node->key);
        free(node), node=NULL;
        fprintf(stderr, "[%s][%d] errmsg:[%d] %s\n", __FILE__, __LINE__, errno, strerror(errno));
        return NULL;
    }

    return node;
}
代码7 新建结点

2.4 结果展示


  只需写一个简单的测试函数，调用以上的测试接口。随机插入n个关键字，并打印其树形结构，便可很方便的判断出插入操作的正确性。
算法导论 之 B-树(B树) - 创建 插入[C语言]
图8 结果展示

作者：邹祁峰
2014.03.13 18:28

算法导论 之 B-树(B树) - 创建 插入[C语言],布布扣,bubuko.com

算法导论 之 B-树(B树) - 创建 插入[C语言]

上一篇：Java编码规范


下一篇：重新整理 .net core 实践篇————cookie 安全问题[三十八]