进阶数据结构 BTree 的插入与删除操作实现

在这里插入图片描述

在数据库系统和文件系统中,高效的数据组织与管理是关键之一。B-Tree(Balanced Tree)作为一种平衡搜索树结构,在这一领域发挥着重要作用。本文详细探讨了 B-Tree 的基本概念以及对其进行插入与删除操作的实现,旨在帮助读者理解 B-Tree 的工作原理以及如何有效地维护这种数据结构。

01 相关概念


B 树(B-tree)是一种常用的自平衡搜索树数据结构。相较于二叉搜索树(Binary Search Tree,BST)每个节点最多有两个子节点的简单设计,B 树则是一种多路搜索树,每个节点可以包含多个子节点,这种多路性使得 B 树更适合在外部存储上存储和管理大量数据,以及处理范围查询。

B 树的设计旨在提供对大量数据的高效检索和插入操作,由于 B 树的自平衡性使得树的高度保持在一个相对稳定的水平,这让插入、删除和检索操作的时间复杂度仅为O(logn),这种高效的操作通常适用于数据库系统和文件系统等需要大规模存储和检索数据的场景。
一颗简单的 B-tree 如下图所示,这是一个 3 阶的 B 树

在这里插入图片描述

如上图中颜色划分 B 树中通常包括三类节点:

  • 根节点(Root Node):根节点是 B 树的顶层节点,位于树的最上方,包含指向树中其他节点的子节点的指针,在搜索操作中,搜索通常从根节点开始。
  • 内部节点(Internal Node):内部节点是树中除了根节点和叶子节点之外的节点,它们包含关键字(key)和子节点指针(pointer),内部节点用于导航到树的其他部分,其中,关键字按值有序排列,用于进行二分搜索,以确定需要访问的子节点。
  • 叶子节点(Leaf Node): 叶子节点是树中最底层的节点,它们不包含子节点指针,它们通常包含实际的数据或指向数据的指针。

一颗 B 树的性质如下:

  • 所有叶子节点(Leaf Node)位于同一层
  • 每个内部节点可以有多个子节点,但最多只能有 m 个子节点,m 通常被称为阶(order),m 的取值通常由磁盘的 block size 决定。
  • 所有节点中,其关键字(key)的个数为其子节点个数减 1
  • 除根节点外,每个节点无论内部节点或叶子节点都至少有 m/2 - 1 和至多 m-1 个关键字,即节点中关键字的数量在 [m/2 - 1, m-1] 之间,换言之,内部节点具有的子节点指针数量为 [m/2, m],为了方便的表示,我们假设 t=m/2 那么节点关键字的数量范围为[t-1, 2t-1]
  • 节点中的所有关键字按升序排列,相邻两个关键字之间包含了关键字处于该范围内的所有子节点的关键字,换言之,一个关键字比它的左子树中的所有关键字值都大,比右子树中所有的关键字值都小

按照上述定义,B 树的结构体定义和相关操作如下

#ifndef _BTREE_H
#define _BTREE_H

#define MIN_T 3
#define MAX_T (MIN_T * 2)

typedef int KeyType;

typedef struct BTreeNodeData /* 结构体声明和 typedef 定义的区别;结构体定义和匿名结构体的含义? */
{
    int         key_num;
    KeyType     key[MAX_T - 1];
    int         leaf;
    struct BTreeNodeData*  child[MAX_T]; /* 结构体嵌套;结构体自引用怎么定义?;声明为 BTreeNode 和 BTreeNode* 的区别是什么 */
} BTreeNode;

typedef struct
{
    BTreeNode*  root;
} BTree;

void btree_create(BTree* tree);	            //初始化树
void btree_level_traverse(BTreeNode* node);            //遍历树
void btree_split_child(BTreeNode* node, int location);	//分裂子结点
void btree_insert_nonfull(BTreeNode* node, int key);	//向未满结点插入关键字
void btree_insert(BTree* tree, int key);	//向树插入关键字

void btree_remove_from_internal(BTreeNode* node, int location);	//删除内部节点中的关键字
void btree_remove_from_leaf(BTreeNode* node, int location);	//删除叶子节点中的关键字
void btree_remove(BTreeNode* node, int key);	//删除树中的关键字

void btree_borrow_from_prev(BTreeNode* node, int location); // 借用 node->child[location - 1] 子树的关键字
void btree_borrow_from_next(BTreeNode* node, int location); // 借用 node->child[location + 1] 子树的关键字
void btree_merge(BTreeNode* node, int location);
void btree_rebalance(BTreeNode* node, int location); //调整关键字所在节点的相关子树和关键字实现再平衡

#endif

02 插入数据


B 树的插入操作是一个相对复杂的过程,因为它需要维护树的平衡性。

向 B 树中插入数据时,可能会导致被插入节点的关键字值数量超过 2t-1 的上限,当插入操作引起该情况时就需要进行分裂(split)操作,整个插入过程可能会导致树的高度增加,但B树的自平衡性质保证了树的高度相对平衡,从而维持了检索性能。

插入操作一般步骤如下:

  1. 搜索插入位置: 从树的根节点开始,按照二分搜索的方式找到合适的叶子节点,该节点将成为新数据的插入位置。在搜索的过程中,也要记录经过的内部节点,这可能在后续的平衡调整中用到。
  2. 插入数据: 在找到叶子节点后,将新的关键字插入到叶子节点中。如果插入导致节点关键字个数超过阶(即节点溢出),则进行分裂操作。
  3. 分裂操作: 如果叶子节点溢出,将该节点的关键字按中间位置分成两部分,其中一部分保留在原节点,另一部分放入一个新节点。中间关键字被提升到父节点,并继续递归向上检查父节点是否溢出。
  4. 父节点的插入和分裂: 如果父节点也溢出,递归进行插入和分裂。这可能会导致分裂一系列的内部节点,一直到根节点。
  5. 根节点分裂: 如果根节点也分裂,需要创建一个新的根节点,将分裂出的两个子节点作为新根的子节点,并更新根节点的关键字。

例如,构造一个 6 阶 B 树,依次插入 10, 20, 30, 40, 50, 60 这 6 个值

首先,在根节点为空的时候初始化 root 并向其中插入值 10,然后不断的向 root 节点插入数值直到达到关键字数量限制 6 - 1 = 5

在这里插入图片描述

当继续插入第 6 个值 60 时,root 节点的关键字个数超过了关键字数量限制,则需要对 root 节点进行分裂,分裂过程如下图所示,原节点一分为二,并且将中间关键字提升到新的根节点中

在这里插入图片描述

上如过程的代码实现如下:

void btree_insert(BTree* tree, int key)
{
    /* BTree 根节点为空时,初始化根节点 */
    if (tree->root == NULL)
    {
        btree_create(tree);

        tree->root->key[0] = key;
        tree->root->key_num = 1;
        tree->root->leaf = 1;
    }
    else
    {
        /* root 满的情况下,创建新的根节点 */
        if (tree->root->key_num == MAX_T - 1)
        {
            BTreeNode* new_root = malloc(sizeof(BTreeNode));
            new_root->child[0] = tree->root;
            new_root->leaf = 0;

            /* 根节点分裂 */
            btree_split_child(new_root,0);

            /* 向分裂后的结构中插入 key */
            int i = 0;
            if (new_root->key[0] < key)
            {
                i++;
            }
            btree_insert_nonfull(new_root->child[i], key);
            
            tree->root = new_root;
        }
        else
        {
            /* root 没满的情况下,从 root 开始查找关键字的插入位置并插入数据 */
            btree_insert_nonfull(tree->root, key);
        }
    }   
}

所以,在 B 树插入操作中涉及两个核心步骤:(1)节点数据未满时的数据插入(2)节点数据已满时的节点分裂

2.1 未满节点插入数据

B 树的插入策略是将新的关键字插入到树中的最底层,即叶子节点。在按关键字递归寻找合适的叶子节点过程中,如果发现节点是已满的情况则对其进行分裂,直到找到未满且合适的叶子节点,找到该节点中关键字插入位置并插入数据。

上如过程代码实现如下:

void btree_insert_nonfull(BTreeNode* node, int key)
{
    int i = node->key_num - 1;

    /* 在叶子节点中插入数据 */
    if (node->leaf)
    {
        /**
         * 1. 找到插入数据的位置
         * 2. 将所有值更大的关键字右移一位
         */
        while (i >= 0 && node->key[i] > key)
        {
            node->key[i+1] = node->key[i];
            i--;
        }
        
        node->key[i+1] = key;
        node->key_num++;
    }
    else
    {
        /* 根据 key 值找到可插入新数据的子节点 */
        while (i >= 0 && node->key[i] > key)
        {
            i--;
        }

        /* 子节点满的情况下,进行分裂 */
        if (node->child[i+1]->key_num == MAX_T - 1)
        {
            btree_split_child(node->child[i+1], i+1);

            if (node->key[i+1] < key)
            {
                i++;
            }
        }
        
        btree_insert_nonfull(node->child[i+1], key);   
    }
}

2.2 已满节点进行分裂

B 树中的节点分裂是在插入操作中用于保持树的平衡性的一种机制。节点分裂的过程会涉及三个节点:被分裂节点、存储被分出部分数据的新节点、被分裂节点的父节点;分裂过程中将被分裂节点的关键字分成两部分,然后将其中一部分放入一个新的节点,同时将中间的关键字提升到父节点,详细过程如下:

  1. 父节点作为输入:被分裂节点根据父节点 node 和其在父节点中的位置 location 决定,即 node->child[location]
  2. 创建新节点: 创建一个新的节点 new_node,用来存放原节点中一半的关键字,所以新节点与被分裂节点处于同一层,其关键字个数为上限的一半。
  3. 关键字分配: 将被分裂节点中的关键字按照中间位置进行分配,一半的关键字保留在原节点,另一半放入新节点;如果原节点是非叶子节点,则需要将被分配关键字对应的子节点也移到新节点下。其中,中间关键字将被提升到父节点。
  4. 更新父节点: 将中间关键字插入到原节点的父节点中,同时将新节点 new_node 加入到父节点 node 的子节点中。

上如过程代码实现如下:

void btree_split_child(BTreeNode* node, int location)
{
    BTreeNode* child = node->child[location];
    BTreeNode* new_node = malloc(sizeof(BTreeNode));
    new_node->leaf = child->leaf;
    new_node->key_num = MIN_T - 1;

    /* 拷贝 child 的 [t,2t-1] 的关键字到 new_node */
    for (int i = 0; i < MIN_T - 1; i++)
    {
        new_node->key[i] = child->key[i + MIN_T];
    }

    /* 如果 child 是非叶子节点,还需要修改 [t,2t] 的子节点*/
    if (!child->leaf)
    {
        for (int i = 0; i < MIN_T; i++)
        {
            new_node->child[i] = child->child[i + MIN_T];
        }
    }

    /* 拷贝完成之后修改 node 的关键字数 */
    child->key_num = MIN_T - 1;
    
    /* 将 node 的子节点从 location 开始向后移动一位 */
    for (int i = node->key_num; i >= location + 1; i--)
    {
        node->child[i+1] = node->child[i];
    }

    /* 将 new_node 插入到 node 的子节点中 */
    node->child[location + 1] = new_node;
    
    /* 将 node 的关键字从 location 开始向后移动一位 */
    for (int i = node->key_num-1; i >= location; i--)
    {
        node->key[i+1] = node->key[i];
    }

    node->key[location] = child->key[MIN_T-1];

    node->key_num++;
}

03 删除数据


B 树的删除操作相对比插入操作更为复杂,因为除了直接从叶子节点上删除对应关键字的情况,还需要考虑在内部节点删除关键字之后 B 树的平衡性被打破,这时就需要重新分配子节点和关键字达到新的平衡。

根据被删除数据所处位置,可将 B 树的删除操作分为两种情况:

1. 被删除数据位于叶子节点: 如果要删除的关键字位于叶子节点上,直接删除关键字。但是,删除关键字之后会出现两种情况:(1)删除数据之后节点仍满足 [t-1, 2t-1] 的平衡条件,不做处理;(2)删除数据之后节点不满足 [t-1, 2t-1]的平衡条件,需要对 B 树进行再平衡操作。
2. 被删除数据位于内部节点: 如果要删除的关键字位于内部节点上,在删除关键字时就会导致其对应的左右子树发生变化:(1)被删除关键字左右子树有足够的数据数量,只需要借用左右相邻子树节点中数据顶替内部节点中被删除关键字即可;(2)被删除关键字左右子树都不满足 [t-1, 2t-1] 的平衡条件,则直接删除该关键字且合并左右相邻子树节点减少该内部节点子节点数量。

下面以如下 6 阶 B 树为例,其关键字平衡条件为 [2,5],介绍 B 树删除操作中的五种情况,图片构造来源:B-Tree Visualization

在这里插入图片描述


第一种情况,被删除数据位于叶子节点,且删除数据后叶子节点仍满足平衡条件:删除 C

自根节点开始搜索要删除的关键字 C

在这里插入图片描述

删除关键字 C 之后,该叶子节点关键字个数为 2 满足平衡条件,删除操作完成

在这里插入图片描述


第二种情况,被删除数据位于内部节点,且左右相邻子树节点中存在足够数据数量的子节点:删除 H

接着,继续删除内部节点中的关键字 H,自根节点开始搜索找到 H 所在的内部节点

在这里插入图片描述

删除内部节点中的关键字 H,并从该关键字对应的左子树的节点中借用最大的关键字 G 替换被删除的 H

在这里插入图片描述

左子树节点中的关键字 G借用之后,该节点关键字个数为 2 满足平衡条件,删除操作完成

在这里插入图片描述


第三种情况,被删除数据位于内部节点,但左右相邻子树节点的关键字个数都是 t-1:删除 D

继续删除内部节点中的关键字 D,自根节点开始搜索找到 D 所在的内部节点

在这里插入图片描述

删除内部节点中的关键字 D,并从该关键字对应的左子树的节点中借用最大的关键字 B 替换被删除的 D

在这里插入图片描述

左子树节点中的关键字 B 被借用之后,该节点关键字个数为 1 不满足平衡条件,而右子树节点中的关键字个数仅为 2,如果被借用一个关键字也会出现不满足平衡条件的情况。这时,放弃从左右子树借用关键字,只能将左右子树进行合并

在这里插入图片描述

直接删除内部节点的关键字 D,关键字 B 下降并将其左右子树合并,删除操作完成

在这里插入图片描述


第四种情况,被删除数据位于叶子节点,且该叶子节点的关键字个数为 t-1,但该叶子节点的父节点和兄弟节点关键字都有足够的数据数量即关键字个数大于 t-1删除 U

继续删除叶子节点中的关键字 U,自根节点开始搜索找到 U 所在的叶子节点,其父节点关键字个数为 3,兄弟节点 X Y Z 的关键字个数也为 3,均大于平衡条件下限 2

在这里插入图片描述

删除关键字 U 之后,该叶子节点关键字个数为 1 不满足平衡条件,但是其父节点有足够的关键字。这时,从父节点下降最小的关键字到该节点以替换被删除的关键字 O;接着,如果其兄弟节点即父节点的右子树节点中有足够数量关键字,则借用一个最小值到父节点

在这里插入图片描述

从父节点将关键字 W 下降替换被删除的关键字 U,然后从兄弟节点借用关键字 X,删除操作完成

在这里插入图片描述

上述过程还存在另一种情况:被删除数据位于叶子节点,且该叶子节点及其兄弟节点的关键字个数为 t-1,但该叶子节点的父节点有足够的数据数量即关键字个数大于 t-1:删除 O

继续删除叶子节点中的关键字 O,自根节点开始搜索找到 O 所在的叶子节点,兄弟节点 R S 的关键字个数为 2 不可被借用,其父节点关键字个数为 3 大于平衡条件下限 2

在这里插入图片描述

删除关键字 O 之后该叶子节点不满足平衡条件需要进行调整,这时兄弟节点关键个数仅为 t-1,则需要与兄弟节点进行合并

在这里插入图片描述

从父节点将关键字 Q 下降替换被删除的关键字 O,然后与兄弟节点合并,删除操作完成

在这里插入图片描述


第五种情况,被删除数据位于叶子节点,且该叶子节点的关键字个数为 t-1,但该叶子节点的父节点关键字也为 t-1删除 M

继续删除叶子节点中的关键字 M,自根节点开始搜索找到 M 所在的叶子节点

在这里插入图片描述

删除关键字 M 之后,其父节点关键字个数为 2,兄弟节点 I J 的关键字个数也为 2,均无法进行借用

在这里插入图片描述

但是,删除关键字 M 之后该叶子节点不满足平衡条件需要进行调整,这时兄弟节点关键个数仅为 t-1,则需要与兄弟节点进行合并。将父节点中的关键字 K 下降,然后将左右子树合并

在这里插入图片描述

合并完成之后,父节点不满足平衡条件需要进行回溯调整,父节点的兄弟节点 T X 的关键字个数也仅为 t-1,无法借用则进一步进行合并操作

在这里插入图片描述

父节点与其兄弟节点的合并过程同理,将祖节点关键字 N 下降,然后合并该节点的左右子树,删除操作完成

在这里插入图片描述

所以,B 树的删除操作包括两种主要情况:(1)在叶子节点中删除关键字(2)在内部节点中删除关键字;

B 树的删除操作包括两种主要操作:(1)向相邻或兄弟节点借用关键字(2)与相邻或兄弟节点合并


3.1 删除操作实现

B 树的删除操作从根节点开始根据目标值找到要删除关键字所在节点的位置,并根据查找结果判断是否在当前节点进行删除操作,如果关键字不在当前节点则递归在子树中进行删除操作直到完成数据删除,详细过程如下:

  1. 寻找关键字的位置:通过循环遍历节点的关键字,找到第一个大于或等于目标值 key 的位置 location
  2. 关键字在当前节点中:如果找到了关键字,则根据节点是叶子节点还是内部节点来调用不同的删除函数
    • 如果是叶子节点,调用 btree_remove_from_leaf 函数删除关键字。
    • 如果是内部节点,调用 btree_remove_from_internal 函数删除关键字。
  3. 关键字在子树中:
    • 如果当前节点是叶子节点且关键字不存在,则表示 B 树内不存在该关键字函数返回。
    • 如果当前节点是内部节点,则需要进一步处理。首先,判断关键字所在的子树是否需要进行再平衡,通过检查子树的关键字数量是否小于 B 树阶数的一半来实现的,如果需要再平衡,调用 btree_rebalance 函数进行再平衡。
    • 根据关键字的位置和是否在最后一个关键字的子树中,递归调用 btree_remove 函数来在子树中删除关键字。

上如过程代码实现如下:

void btree_remove(BTreeNode* node, int key)
{
    if (node == NULL)
    {
        return;
    }

    /* 寻找关键字的位置 */
    int location = 0;
    while (location < node->key_num && node->key[location] < key)
    {
        location++;
    }

    /*  要删除的关键字在当前节点 node 中 */
    if (location < node->key_num && node->key[location] == key)
    {
        /* 如果 node 是叶子节点,调用 btree_remove_from_leaf 删除关键字 */
        if (node->leaf)
        {
            btree_remove_from_leaf(node, location);
        }
        else
        {
            /* 如果 node 是内部节点,调用 btree_remove_from_internal 删除关键字 */
            btree_remove_from_internal(node, location);
        }
    }
    else
    {
        /*  要删除的关键字在子树中 */
        if (node->leaf)
        {
            /* node 是叶子节点,该关键不存在*/
            return;
        }

        /* flag 记录是否在是最后一个关键字的子树中 */
        bool flag = ((location == node->key_num)? true : false);

        /* node 的关键字个数少于 B 树阶数一半,则需要进行再平衡 */
        if (node->child[location]->key_num < MIN_T)
        {
            btree_rebalance(node, location);
        }

        if (flag && location > node->key_num)
        {
            btree_remove(node->child[location - 1], key);
        }
        else
        {
            btree_remove(node->child[location], key);
        }
    }

    return;
}

第一种情况直接从 B 树的叶子节点中删除关键字,叶子节点不包含子节点,在删除叶子节点中的关键字时,只需要将关键字之后的所有关键字向左移动一位,以填补删除关键字后留下的空位,并更新关键字的数量。

void btree_remove_from_leaf(BTreeNode* node, int location)
{
    for (int i = location + 1; i < node->key_num; i++)
    {
        node->key[i - 1] = node->key[i];
    }

    node->key_num--;
    
    return;
}

第二种情况从内部节点中删除关键字,当从内部节点删除一个关键字时,需要通过借用关键字或合并子节点来维护 B 树的平衡性。

  1. 借用相邻左右子树节点的关键字:如果左右子树子节点中的关键字数量大于或等于 t,则可以从子树借用一个关键字来替代要删除的关键字。
  2. 合并子节点:如果左右子节点的关键字数量都小于 t,则必须进行子节点的合并。调用 btree_merge 函数来合并左右子节点,并重新平衡 B 树。
void btree_remove_from_internal(BTreeNode* node, int location)
{
    KeyType key = node->key[location];
    BTreeNode* cur = NULL; 

    /* 如果子节点的 key_num 大于 MIN_T,那么从子节点中借用一个关键字 */
    if (node->child[location]->key_num >= MIN_T)
    {
        cur = node->child[location];
        while (!cur->leaf)
        {
            cur = cur->child[cur->key_num];
        }

        KeyType pred = cur->key[cur->key_num - 1];
        node->key[location] = pred;
        btree_remove(node->child[location], pred);
    }
    else if (node->child[location + 1]->key_num >= MIN_T)
    {
        cur = node->child[location + 1];
        while (!cur->leaf)
        {
            cur = cur->child[0];
        }

        KeyType succ = cur->key[0];
        node->key[location] = succ;
        btree_remove(node->child[location + 1], succ);
    }
    else /* 子节点关键字数量都小于 MIN_T,需要合并子节点 */
    {
        btree_merge(node, location);
        btree_remove(node, key);
    }
    
    return;
}

3.2 借用与合并操作实现

借用和合并操作是维护 B 树平衡性的关键步骤,当从 B 树删除一个关键字后,可能会导致该节点的关键字数量小于 B 树的阶数的一半 t,这时就需要重新平衡该节点。

重新平衡通常涉及从其他节点借用关键字或合并节点,该过程的实现依赖于 btree_borrow_from_prevbtree_borrow_from_nextbtree_merge这些函数,这些函数分别负责从前一个兄弟节点借用关键字、从后一个兄弟节点借用关键字和合并相邻的兄弟节点。

void btree_rebalance(BTreeNode* node, int location)
{
    if (location != 0 && node->child[location - 1]->key_num >= MIN_T)   // 借用 node->child[location - 1] 子树的关键字
    {
        btree_borrow_from_prev(node, location);
    }
    else if (location != node->key_num && node->child[location + 1]->key_num >= MIN_T) // 借用 node->child[location + 1] 子树的关键字
    {
        btree_borrow_from_next(node, location);
    }
    else
    {
        if (location != node->key_num)
        {
            btree_merge(node, location);
        }
        else
        {
            btree_merge(node, location - 1);
        }
    }
    
    return; 
}

btree_borrow_from_prev 函数用于从一个节点的前一个兄弟节点借用一个关键字,该函数实现如下:

  1. 首先,获取 location 位置的子节点 child 和兄弟节点 sibling
  2. 移动子节点 child 的元素,通过循环将 child 节点中的所有元素向右移动一个位置,以便为从兄弟节点借用的关键字腾出空间。
  3. 从兄弟节点借用关键字,将当前节点的 location - 1 位置的关键字移动到 child 节点的第一个位置并使用兄弟节点 sibling 的最后一个值替换该节点;如果 child 节点不是叶子节点,则将兄弟节点的最后一个孩子节点复制到 child 节点的第一个孩子位置。
void btree_borrow_from_prev(BTreeNode* node, int location)
{
    BTreeNode* child = node->child[location];
    BTreeNode* sibling = node->child[location - 1];

    for (int i = child->key_num - 1; i >= 0; --i)
    {
        child->key[location + i] = child->key[i];
        if (!child->leaf)
        {
            child->child[i + 1] = child->child[i];
        }
    }

    child->key[0] = node->key[location - 1];
    
    if (!child->leaf)
    {
        child->child[0] = sibling->child[sibling->key_num];
    }
    
    node->key[location - 1] = sibling->key[sibling->key_num - 1];

    child->key_num++;
    sibling->key_num--;
    
    return;
}

btree_borrow_from_next 函数用于从节点的后一个兄弟节点借用一个关键字,该函数实现 btree_borrow_from_pred 相似,首先使用当前节点 location 位置的关键字替换 child 节点的最后一个位置并使用兄弟节点 sibling 的第一个值覆盖该节点,然后将兄弟节点 sibling 的关键字和子节点(若非叶子节点)都向前移动一位。

void btree_borrow_from_next(BTreeNode* node, int location)
{
    BTreeNode* child = node->child[location];
    BTreeNode* sibling = node->child[location + 1];

    child->key[child->key_num] = node->key[location];

    if (!child->leaf)
    {
        child->child[child->key_num + 1] = sibling->child[0];
    }

    node->key[location] = sibling->key[0];

    for (int i = 1; i < sibling->key_num; ++i)
    {
        sibling->key[i - 1] = sibling->key[i];
        if (!child->leaf)
        {
            sibling->child[i - 1] = sibling->child[i];
        }
    }

    child->key_num++;
    sibling->key_num--;

    return;
}

btree_merge 函数是合并操作的实现,将一个节点及其所有关键字和孩子节点合并到相邻的兄弟节点中,然后删除空的节点,其实现过程如下:

  1. 获取当前节点在 location 位置的子节点 child 和下一个兄弟节点 sibling
  2. 移动关键字和孩子节点,将当前节点在 location 位置的关键字移动到 child 节点的 t-1 位置,并通过循环将 sibling 节点的所有关键字和孩子节点复制到 child 节点中
  3. 移动当前节点的关键字和孩子节点,通过循环将当前节点从 location + 1key_num 的所有关键字和孩子节点分别向左移动一个位置
  4. 更新关键字和子节点的数量
void btree_merge(BTreeNode* node, int location)
{
    BTreeNode* child = node->child[location];
    BTreeNode* sibling = node->child[location + 1];

    child->key[MIN_T - 1] = node->key[location];

    for (int i = 0; i < sibling->key_num; ++i)
    {
        child->key[i + MIN_T] = sibling->key[i];
        if (!child->leaf)
        {
            child->child[i + MIN_T] = sibling->child[i];
        }
    }

    for (int i = location + 1; i < node->key_num; ++i)
    {
        node->key[i - 1] = node->key[i];
    }

    for (int i = location + 2; i <= node->key_num; ++i)
    {
        node->child[i - 2] = node->child[i];
    }

    child->key_num += sibling->key_num + 1;
    node->key_num--;

    free(sibling);
    return;
}

如果文章对你有帮助,欢迎一键三连 👍 ⭐️ 💬 。如果还能够点击关注,那真的是对我最大的鼓励 🔥 🔥 🔥 。


参考资料

https://www.cs.usfca.edu/~galles/visualization/BTree.html
https://www.geeksforgeeks.org/introduction-of-b-tree-2/?ref=lbp
https://www.geeksforgeeks.org/insert-operation-in-b-tree/?ref=lbp
https://www.geeksforgeeks.org/delete-operation-in-b-tree/?ref=lbp
https://www.cnblogs.com/nullzx/p/8729425.html
https://cloud.tencent.com/developer/article/1127427?from=15425
https://www.codedump.info/post/20200609-btree-1/

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/409947.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

kubectl使用及源码阅读

目录 概述实践样例yaml 中的必须字段 kubectl 代码原理kubectl 命令行设置pprof 抓取火焰图kubectl 中的 cobra 七大分组命令kubectl createcreateCmd中的builder模式createCmd中的visitor访问者模式外层VisitorFunc分析 结束 概述 k8s 版本 v1.24.16 kubectl的职责 1.主要的…

供应链大数据:穿越经济迷雾的指南针

随着经济形势的变幻莫测&#xff0c;企业运营面临着前所未有的挑战。在这个充满不确定性的时代&#xff0c;供应链大数据如同一盏明亮的指南针&#xff0c;为企业提供精准的方向指引。下面&#xff0c;我们将深入探讨供应链大数据如何帮助企业洞察市场趋势、优化库存管理、降低…

2024年ODE(云端集成开发环境)排行榜

✍️作者简介&#xff1a;小北编程&#xff08;专注于HarmonyOS、Android、Java、Web、TCP/IP等技术方向&#xff09; &#x1f433;博客主页&#xff1a; 开源中国、稀土掘金、51cto博客、博客园、知乎、简书、慕课网、CSDN &#x1f514;如果文章对您些帮助请&#x1f449;关…

获取tensorflow lite模型指定中间层的输出

以mobilenet v2为例子&#xff0c;我已经训练好了模型&#xff0c;有tflite格式和onnx格式两种模型的权重文件&#xff0c;我想获取tflite模型在推理阶段neck部分的输出。 查看onnx模型得到neck最后一层位置 使用netron查看onnx模型结构 从name中能知道Reshape是neck的最后一…

[c++] char * 和 std::string

1 char * 和 std::string 的区别 char * 字符串是常量字符串&#xff0c;不能修改&#xff1b;std::string 指向的字符串可以修改 实例代码如下图所示&#xff0c;s1 和 s2 均是常量字符串&#xff0c;字符串常量保存在只读数据区&#xff0c;是只读的&#xff0c;不能写&…

QT GUI编程常用控件学习

1 GUI编程应该学什么 2 QT常用模块结构 QtCore: 包含了核心的非GUI的功能。主要和时间、文件与文件夹、各种数据、流、URLs、mime类文件、进程与线程一起使用 QtGui: 包含了窗口系统、事件处理、2D图像、基本绘画、字体和文字类 QtWidgets: 包含了一些列创建桌面应用的UI元素…

python input 输入

input()函数包含四个方面&#xff1a;input()函数的使用/结果的赋值/数据类型/结果的强制转换。是实现人机互动沟通的关键&#xff0c;需要在终端出输入信息。我们可以把input()函数当作一扇链接现实世界与代码世界的门&#xff0c; 如下图 先看一个例子&#xff1a;  运行后终…

生产线辅料加注机加注量的可视化操作系统无线通讯应用

挖掘机装配生产线在生产过程中&#xff0c;需要在下车装配、液压测试、发动机部件装配等过程中添加液压油、柴油、润滑油、防冻液、冷媒等辅料。加注机作为必要的辅料加注设备&#xff0c;将设定辅料输入到挖掘机对应输送管道中。 客户需求是想实现挖掘机装配线加注机与操作台…

Linux基础命令—系统服务

基础知识 centos系统的开机流程 1)通电 2)BIOS硬件检查 3)MBR引导记录 mbr的引导程序 加载引导程序 让硬件加载操作系统内核 MBR在第一个磁盘第一个扇区 总大小512字节 mbr: 1.引导程序: 占用446字节用于引导硬件,加载引导程序 2.分区表: 总共占…

关系型数据库事务的隔离级别: 读未提交, 读已提交, 可重复读, 序列化。

关系型数据库事务的隔离级别&#xff1a; 读未提交, 读已提交, 可重复读, 序列化。 事务的四性: 原子性&#xff0c;一致性&#xff0c;隔离性&#xff0c;持久性。(4项) 事务的隔离级别&#xff1a; 读未提交, 读已提交, 可重复读, 序列化。(4项) 并发事务可能引起: 脏读, …

【计算机网络】1.4 接入网和物理媒体

1.4 接入网和物理媒体 问题&#xff1a;怎样将端系统和边缘路由器连接&#xff1f; 答&#xff1a;有线方式&#xff08;住宅接入网络、单位接入网络等&#xff09;或无线方式&#xff08;无线接入网络&#xff09;。 有线接入方式 光纤同轴混合网是基于已有的有线电视网开发的…

中年人,收起你的大方

作者| Mr.K 编辑| Emma 来源| 技术领导力(ID&#xff1a;jishulingdaoli) 先和大家分享一件最近发生在K哥身上的真实故事。K哥前同事老G托我帮他一位朋友推荐工作&#xff0c;说他的这个朋友失业好几个月了&#xff0c;上有老下有小很不容易&#xff0c;让我无论如何也要想办…

IDEA安装配置以及安装配置Maven

IEDA官方下载地址&#xff0c;有专业版&#xff08;收费&#xff0c;破解&#xff09;&#xff0c;社区版&#xff08;免费&#xff09; 下载 IntelliJ IDEA – 领先的 Java 和 Kotlin IDE 安装配置Maven 1.解压apache-maven-3.6.3-bin.zip&#xff0c;安装maven到D盘softwar…

【YOLO v5 v7 v8小目标改进】SPD-Conv

SPD-Conv 提出背景SPD-Conv YOLO v5 小目标改进定义 SPD-Conv导入SPD模块修改 .yaml 文件 YOLO v7 小目标改进YOLO v8 小目标改进 提出背景 论文&#xff1a;https://arxiv.org/pdf/2208.03641v1.pdf 代码&#xff1a;https://github.com/labsaint/spd-conv 文章提出一个新的…

代码随想录算法刷题训练营day23

代码随想录算法刷题训练营day23&#xff1a;LeetCode(669)修剪二叉搜索树、LeetCode(108)将有序数组转换为二叉搜索树、LeetCode(538)把二叉树转化为累加树 LeetCode(669)修剪二叉搜索树 题目 代码 /*** Definition for a binary tree node.* public class TreeNode {* …

数据安全之路:深入了解MySQL的行锁与表锁机制

欢迎来到我的博客&#xff0c;代码的世界里&#xff0c;每一行都是一个故事 数据安全之路&#xff1a;深入了解MySQL的行锁与表锁机制 前言基础innodb中锁与索引的关系如何避免表锁 前言 在当今数据密集的应用中&#xff0c;数据库锁成为了确保数据一致性和并发操作的关键工具…

Linux字符设备驱动中同类型多设备节点的创建---一个驱动程序支持多个同类型设备

文章目录 前言1 代码解析1.1 驱动层1.2 应用层 2 运行结果总结 前言 本期分享的内容相对比较简单&#xff0c;那就是同时注册多个同类型的字符设备驱动&#xff0c;那么这样我们就可以同时支持多个同类型的设备了&#xff01;下面来带大家看一下&#xff1a; 1 代码解析 1.1 …

【Flink精讲】Flink性能调优:内存调优

内存调优 内存模型 JVM 特定内存 JVM 本身使用的内存&#xff0c;包含 JVM 的 metaspace 和 over-head 1&#xff09; JVM metaspace&#xff1a; JVM 元空间 taskmanager.memory.jvm-metaspace.size&#xff0c;默认 256mb 2&#xff09; JVM over-head 执行开销&#xff1…

深入探讨基于大语言模型的数据标注

文章地址&#xff1a; https://arxiv.org/pdf/2402.13446 数据标注是将原始数据用相关信息进行标注&#xff0c;对于提高机器学习模型的效果至关重要。然而&#xff0c;这一过程往往需要大量人力和资金支持。先进大语言模型&#xff08;LLMs&#xff09;的出现&#xff0c;例如…

小程序--事件处理

一、事件对象 给小程序的事件传递参数&#xff0c;有以下两种方法&#xff1a; 1、自定义属性 <view class"item" wx:for"{{ 5 }}" wx:key"*this" data-index"{{index}}" bind:tap"onClick"></view> Page({o…