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

2024-02-26 14:04
文章标签 进阶 实现 操作 数据结构 删除 插入 btree

本文主要是介绍进阶数据结构 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_prev、btree_borrow_from_next 和 btree_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 + 1 到 key_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/

这篇关于进阶数据结构 BTree 的插入与删除操作实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/749108。

相关文章

C++使用栈实现括号匹配的代码详解

C++使用栈实现括号匹配的代码详解

《C++使用栈实现括号匹配的代码详解》在编程中,括号匹配是一个常见问题,尤其是在处理数学表达式、编译器解析等任务时,栈是一种非常适合处理此类问题的数据结构,能够精确地管理括号的匹配问题,本文将通过C+... 目录引言问题描述代码讲解代码解析栈的状态表示测试总结引言在编程中，括号匹配是一个常见问题，尤其是在
阅读更多...
Python调用Orator ORM进行数据库操作

Python调用Orator ORM进行数据库操作

《Python调用OratorORM进行数据库操作》OratorORM是一个功能丰富且灵活的PythonORM库,旨在简化数据库操作,它支持多种数据库并提供了简洁且直观的API,下面我们就... 目录Orator ORM 主要特点安装使用示例总结Orator ORM 是一个功能丰富且灵活的 python O
阅读更多...
Java实现检查多个时间段是否有重合

Java实现检查多个时间段是否有重合

《Java实现检查多个时间段是否有重合》这篇文章主要为大家详细介绍了如何使用Java实现检查多个时间段是否有重合,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录流程概述步骤详解China编程步骤1：定义时间段类步骤2：添加时间段步骤3：检查时间段是否有重合步骤4：输出结果示例代码结语作
阅读更多...
使用C++实现链表元素的反转

使用C++实现链表元素的反转

《使用C++实现链表元素的反转》反转链表是链表操作中一个经典的问题,也是面试中常见的考题,本文将从思路到实现一步步地讲解如何实现链表的反转,帮助初学者理解这一操作,我们将使用C++代码演示具体实现,同... 目录问题定义思路分析代码实现带头节点的链表代码讲解其他实现方式时间和空间复杂度分析总结问题定义给定
阅读更多...
Java覆盖第三方jar包中的某一个类的实现方法

Java覆盖第三方jar包中的某一个类的实现方法

《Java覆盖第三方jar包中的某一个类的实现方法》在我们日常的开发中,经常需要使用第三方的jar包,有时候我们会发现第三方的jar包中的某一个类有问题,或者我们需要定制化修改其中的逻辑,那么应该如何... 目录一、需求描述二、示例描述三、操作步骤四、验证结果五、实现原理一、需求描述需求描述如下：需要在
阅读更多...
JavaScript中的reduce方法执行过程、使用场景及进阶用法

JavaScript中的reduce方法执行过程、使用场景及进阶用法

《JavaScript中的reduce方法执行过程、使用场景及进阶用法》：本文主要介绍JavaScript中的reduce方法执行过程、使用场景及进阶用法的相关资料,reduce是JavaScri... 目录1. 什么是reduce2. reduce语法2.1 语法2.2 参数说明3. reduce执行过程
阅读更多...
如何使用Java实现请求deepseek

如何使用Java实现请求deepseek

《如何使用Java实现请求deepseek》这篇文章主要为大家详细介绍了如何使用Java实现请求deepseek功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录1.deepseek的api创建2.Java实现请求deepseek2.1 pom文件2.2 json转化文件2.2
阅读更多...
python使用fastapi实现多语言国际化的操作指南

python使用fastapi实现多语言国际化的操作指南

《python使用fastapi实现多语言国际化的操作指南》本文介绍了使用Python和FastAPI实现多语言国际化的操作指南,包括多语言架构技术栈、翻译管理、前端本地化、语言切换机制以及常见陷阱和... 目录多语言国际化实现指南项目多语言架构技术栈目录结构翻译工作流1. 翻译数据存储2. 翻译生成脚本
阅读更多...
如何通过Python实现一个消息队列

如何通过Python实现一个消息队列

《如何通过Python实现一个消息队列》这篇文章主要为大家详细介绍了如何通过Python实现一个简单的消息队列,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录如何通过 python 实现消息队列如何把 http 请求放在队列中执行1. 使用 queue.Queue 和 reque
阅读更多...
Python如何实现PDF隐私信息检测

Python如何实现PDF隐私信息检测

《Python如何实现PDF隐私信息检测》随着越来越多的个人信息以电子形式存储和传输,确保这些信息的安全至关重要,本文将介绍如何使用Python检测PDF文件中的隐私信息,需要的可以参考下... 目录项目背景技术栈代码解析功能说明运行结php果在当今，数据隐私保护变得尤为重要。随着越来越多的个人信息以电子形
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2