01数据结构-B树

前言

磁盘的物理结构你可以理解为一个一个磁道(类似于操场跑道一样)，每个磁道，我们都有一个轴，这个轴可以伸长，我们读一个磁道的时候会有一个扇面，如图我们称为block(块)，意味着，磁盘中的“地址”不像内存那样是连续的地址，而是一个块号，在磁盘中有个磁盘控制器，当操作系统请求读取一个逻辑块，磁盘控制器定位到该块对应的起始扇区，读取这个扇区及后续连续的几个扇区，将数据整合后返回给操作系统。而这一块就不是一个字节了，我们大部分都认为这个块的字节大小是512B。

1.为什么要有B树

我们之前学的BST，AVL，RBTree都是二叉树，高度和数据的量是log2^N的关系，这些树的查找效率很高，但是查找的前提条件是所有的节点都是在内存中，即在内存中进行操作，有的数据太多我们不能存在内存中，我们需要存放在磁盘里，例如数据库中的数据，手机内存(16G+1T)，16G就是我们的内存大小，1个T就是存盘中的大小。类似上面这些大数据我们一般都存在磁盘中。我们对存在数据库中的数据的操作一般都是查找，在查找时，在内存上查找和在磁盘上查找的时间效率就很不一样了。

在内存上查找，找一个节点（数据），在一个内存周期内能找到。
在磁盘上查找，找一个节点（数据），在一个磁盘周期内能找到。

感兴趣的可以去搜一下内存周期和磁盘周期，我这里就简单说一下，内存周期比磁盘周期大概快了5个数量级。内存周期典型值：我们取一个常见的中间值 ~100 纳秒 (ns)。磁盘周期典型值（HDD）：我们取一个平均值 ~10 毫秒 (ms)。

如果我们还是继续沿用二叉搜索树来实现对磁盘数据的构建，那么就会出现问题，如果我们有1000个元素和2000个元素，假设1000个元素放了10层，2000个元素放了11层，我们查找数据用了一个磁盘周期，在数据中读取我们想用的信息又要耗费时间，这种情况下，哪怕只多了一层，也可能多1秒的查找时间，对用户的体验很不好，现在我们就想到一个问题，能不能找到一棵树使其高度很矮，例如只有两三层，这样就使得查找效率很快了呢？如图，我们节点结构体中存多个数据块，每个数据块从小到大，从左到右排列，在某个数据块左边的节点结构体中的数据块统统比该数据块中的值小，相反在某个数据块右边的节点结构体中的数据块统统比该数据块中的值大。

这一个节点如果恰好是一个磁盘单位，我们做一次磁盘IO就刚好把一个块取到了，假设这个节点有100个数据，我取了一个磁盘IO后，取到这一块，我把这一块放到内存上进行快速查找，也就很快能定位出这个数据的情况了

很明显当节点结构中的数据量越多，相应的这个结构所“管理”的数据也越多，即如果一个节点管了7个数据，该节点的下一层一共会有7的平方个数据，这意味着如果是同样的总数据量，一个节点“管理”的数据量越多，树的总高度就该越矮。假设我们有一张表，表中有ID+数据，假设ID能存10个字节，数据能存118个字节，即一条记录128个字节，实际磁盘的一个block能够存储记录的数量是：512/128=4条，即发生一次磁盘IO后，我就能取出4条数据，假设有100条这样的记录，我们就需要100/4=25个block来存储，如果没有任何数据结构的帮助的话，我们进行25次磁盘IO的访问，一次磁盘IO的访问夸张一点说就可能花费1秒中的时间，25次就是25秒的时间，可想而知这个时间效率是很低的，我们希望把block变少，我们就想到了索引。

(先看图中右边的两个表)稠密索引：每一个元素都有一个唯一索引号，用一个eID（10B），p存这个数据在哪一个block（磁盘地址信息）,则一个条索引占16个字节，1个block能够存储的索引数量：512/16=32，即触发一个block，一下子能取32个索引到内存，在内存中就能快速查找，例如我们要找9，我们通过p向磁盘控制器发出控制，定位到磁盘上的位置，然后读出来，这样大大提高了时间效率，我们一共100条记录，需要100条索引块。则我们需要100/32=4block，相比25，这样我们就大大减少了block的数量

这样最低最低的时间效率就是把4个磁盘都搜索完才查找到。但是如果我们再给索引添加一个稀疏索引，例如，图中最左边的表，我们只存1和33的索引中间其余的索引都不存，当我们要找25，发现25大于1小于33，就在中间那一列的1到33中查找，这样我们通过记录关键的稀疏索引，可以把查找范围进一步缩小，例如只需要搜索一个磁盘，这就是我们B树的目的。

2.B树

B树（B-tree），又称多路平衡查找树，B树中所有节点的孩子个数的最大值称为B树的阶，通常用m来表示，当m=2时，就是最常见的二叉搜索树。

一颗m阶的B树定义如下：
1）每个节点最多有m-1个关键字
2）根节点最少可以有1个关键字
3）非根节点至少有ceil(m/2)-1个关键字
4）每个节点中的关键字都按照从小到大的顺序排列，每个关键字的左子树都所有关键字都小于它，而右子树都所有关键字都大于它
5）所有叶子节点都位于同一层，或者说根节点到每个叶子节点的长度相同

上图是一个四阶B树，在实际应用中B树的阶树m都非常大（通常大于100），所以即使存储大量的数据,B树的高度仍然比较小。每个节点中存储了关键字key和关键字对应的数据data以及孩子节点的指针，我们将一个key和其对应的data称为一个记录。

2.1B树查找算法步骤

假设我们要在一棵 m 阶B树中查找关键字 K。

1.从根节点开始：将根节点从磁盘读入内存。

2.在当前节点中搜索：在当前节点的所有键（K₁, K₂, …, K_n）中进行顺序查找或二分查找（因为键是有序的）。查找的目的是找到第一个 ≥ K 的键，或者确定 K 大于所有现有键。

3.判断结果：

情况A：找到目标键

如果在当前节点中找到了某个键 K_i 等于 K，则查找成功，返回该键及其对应的数据（或指针）。

情况B：确定子树

如果当前节点是内部节点（非叶子节点）：

如果 K < K₁，则进入第1个子节点（最左边的子节点）继续查找。

如果 K > K_n，则进入第n+1个子节点（最右边的子节点）继续查找。

如果 K_i < K < K_{i+1}，则进入第i+1个子节点继续查找。

如果当前节点是叶子节点：

如果在叶子节点中也没有找到 K，则说明关键字 K 不在树中，查找失败。

4.递归/迭代：

根据上一步确定的子节点指针，将对应的子节点从磁盘读入内存。重复步骤2和步骤3，直到找到关键字 K 或者确认它不存在（到达叶子节点仍未找到）。

查找过程可视化示例:

查找路径：

访问根节点 [10, 20]：在根节点中搜索 22。22 > 20，因此它应该位于 20 的右侧子树（即第三个子节点）。访问子节点 [25,28,30]：在该节点中搜索 22。22 < 25，因此它应该位于 25 的左侧子树（即第一个子节点）发现空指针：节点 [25,28,30] 的第一个子指针是空的（因为它是叶子节点，没有子节点）。结论：在叶子节点中未找到 22，查找失败，关键字 22 不存在。

另一个示例：查找成功在同一棵树中查找关键字 18。

查找路径：访问根节点 [10, 20]：搜索 18。发现 10 < 18 < 20。因此，进入 10 和 20 之间的子树（即第二个子节点）。访问子节点 [15,18]：在该节点中顺序查找，发现第二个键 18 等于目标值。结论：查找成功！

2.2B树的中序遍历

B树的中序遍历和二叉树的中序遍历也很相似，从最左边的孩子节点开始，递归地打印最左边的孩子节点，然后对剩余的孩子和关键字重复相同的过程，最后递归打印最右边的孩子。

2.3回溯插入法

B树的插入不是简单的递归回溯，而是更巧妙的“先查找路径，再反向分裂” 的策略。这个过程通常使用迭代而非递归来实现，以节省栈空间并更符合磁盘I/O的特性。

核心思想：插入与分裂：

• 1.查找插入位置：首先，像普通的查找一样，从根节点开始，沿着查找路径一直找到应该包含该键的叶子节点。

• 2.插入键：将新的键插入到这个叶子节点中（因为所有数据最终都存储在叶子节点）。

• 3.检查溢出：插入后，检查该节点的键数量是否超过了最大值（m-1）。

• 4.处理溢出（分裂）：如果节点溢出，则将其分裂成两个节点，并选择一个中间键提升到父节点中。这个操作可能会导致父节点溢出，从而需要递归地向上继续分裂，直到不再溢出或到达根节点。

• 5.处理根节点分裂：如果分裂一直回溯到根节点并导致根节点溢出，则创建一个新的根节点，树的高度增加1。

这个“向上分裂”的过程，就是一种从叶子节点向根节点的“回溯”。

如图，图中往下的是插入时需要分裂时的中间过程，假设这颗B树是度为3的树，则一个节点最多两个数据有三个叉，当插入1，2的时候直接插入，当插入3的时候，已经等于度了，需要从中间往上分裂，即将2分离上去，插入4，直接在3旁边插入，插入5时，需要分裂，把中间数据4分裂上去。

插入6没事，插入7时，最下方满了3个把中间数据6往上分裂，发现又等于度3，再次把中间数据4往上分裂，最终如右图所示。

2.4主动插入法

主动插入法（先分裂）的核心思想
主动插入法的策略恰恰相反：

在向下查找插入路径的过程中，只要遇到“满”的节点（键数 == m-1），就立即将其分裂。这样做的目的是确保在插入新键时，它的父节点永远有空间来接收一个可能被提升上来的中间键。

简单来说： 不是等到插入后造成溢出了再处理，而是提前为可能的溢出扫清道路。

主动插入算法步骤：
假设要向一棵 m 阶B树中插入关键字 K。

• 1.从根节点开始：

  如果根节点是满的（键数 == m-1）：

  分裂根节点。创建一个新的根节点，树的高度增加。

  现在，根节点肯定不是满的了。

  设置当前节点为根节点。

• 2.向下查找并主动分裂：

  While 当前节点不是叶子节点 Do:

  找到关键字 K 应该进入的子节点 Child（即找到合适的指针位置）。

  检查子节点 Child：

  如果 Child 是满的（键数 == m-1）:

  立即分裂这个满的子节点。

  将分裂产生的中间键提升并插入到当前节点中。

  更新当前节点中指向子节点的指针（原来指向满子节点的指针被替换为指向分裂后的两个新节点的指针）。

  重要：由于我们提前分裂了，当前节点（父节点）在接收中间键之前肯定不是满的（因为我们正在向下查找，还没开始插入，并且如果父节点之前是满的，它已经被处理过了）。

  如果 Child 不是满的:

  什么都不做。

将当前节点设置为这个子节点 Child，继续向下查找。

• 3.插入叶子节点：

  最终，我们到达一个肯定不是满的叶子节点（因为如果它在路径上是满的，已经被我们提前分裂了）。

  将关键字 K 安全地插入到这个叶子节点中。由于节点不是满的，插入后绝不会溢出，因此不需要任何回溯操作！

如图我们要插入45

第1步：检查根节点并分裂（如果需要）从根节点 [40, 60] 开始。检查发现它是满的（有2个关键字）。必须立即分裂根节点，为后续可能的关键字提升腾出空间。分裂根节点：中间关键字是 40 (对于3阶B树，通常是第一个中间关键字)。左子节点继承小于 40 的关键字：[] (暂时为空，但结构存在)右子节点继承大于 40 的关键字：[60]创建新根节点：新的根节点就是提升上来的 40。

为什么要暂时为：

在最后插入完成之前，那个新分裂出来的空白节点 [] 的最终位置和内容都是不确定的。这个空白节点 [] 就像一个“空位”或“缓冲区”，它的最终命运取决于接下来要插入的关键字的值。因为你不知道新插入的值要往哪个方向走。

此时树的结构：

第2步：向下查找路径并主动分裂现在从新根 [40] 开始查找 45 的插入位置。45 与根节点的 40 比较：45 > 40，所以应该进入右子树 [60]。检查目标子节点 [60]：它不是满的（只有1个关键字 < 2），所以不需要分裂。直接向下进入该节点。

第3步：继续向下在节点 [60] 内决策并分裂其子节点

当前节点是 [60]。在 [60] 内部，根据键 45 < 60，决定下一步要进入它的第一个子节点，即 child_ptr1 指向的 [50,55]。在向下进入 [50,55] 之前，先检查它。发现 [50,55] 是满的。

触发主动分裂：分裂操作由父节点（[60]）发起和执行。分裂完成后，[50,55] 被分裂成三部分：一个要提升的中间键 50，一个新的左子节点 left_child (初始为空 [])，一个新的右子节点 right_child (包含 [55])

父节点接收提升的键：父节点 [60] 将中间键 50 插入到自身的关键字数组中。[60] -> [50, 60]。

父节点更新指针：父节点 [50,60] 更新其子指针。原来指向 [50,55] 的那个指针（child_ptr1）被替换为两个新的指针：child_ptr1 现在指向新创建的 left_child ([])一个新增加的 child_ptr2 指向新创建的 right_child ([55])它原来可能有的其他子指针（比如指向 [70,80] 的指针）顺序后移。

分裂操作结束。注意：当前节点仍然是这个父节点 [50,60]。分裂子节点的操作并没有改变“当前节点”是谁，我们仍然站在 [50,60] 这个节点上，准备继续向下查找。

此时树结构：

第4步：从当前节点 [50,60] 继续向下当前节点现在是 [50,60] (刚刚接收了子节点分裂上来的键)。

我们需要在这个新的当前节点中重新为 45 查找路径：

比较 45 < 50？是的。因此，下一步应该进入 [50,60] 节点的第一个子节点。这个“第一个子节点”就是上一步分裂后新创建的那个左子节点 left_child (也就是空节点 [])。
检查这个子节点 []，它不是满的。所以我们可以安全地向下进入这个节点。现在当前节点变成了这个空叶子节点 []。将 45 插入其中。插入完成。

最终树结构如图：

3. B树数据结构设计

#define  MaxOrder 3           // B树的阶
typedef  int KeyType;         // B树的节点键值类型
/* B树的阶是MaxOrder(3)，说明最大有3棵子树
 * 在插入节点时，当键值数量为3时，进行分离，申请MaxOrder+1，从1索引开始填入键值申请的K3
 * 触发节点存放的个数为3，触发分离现象
 * | k0 | k1 | k2 | k3 |        k0无效，k3防越界
 * | p0 | p1 | p2 | p3 |
 * p0 < k1, k1<p0<k2, p2>k2     p3不访问
 */
// B树的节点结构定义
typedef struct _BTNode{
    KeyType key[MaxOrder+1];            // [1...MaxOrder-1]
    struct _BTNode *ptr[MaxOrder+1];    // 0开始存放关系
    struct _BTNode *parent;             // 指向父节点
    int keyNum;                         // 该节点的键值数量
} BTNode;

typedef struct {
    BTNode *root;
    int count;
} DiskBTree;
#endif //DATASTRUCT_DISK_BTRE

在这里申请MaxOrder+1个空间的原因是：这样设计中，key[0] 是无效的，key[MaxOrder] 用于防越界。这样可以简化插入和分裂操作的实现，减少边界条件的处理复杂度。而如果一个节点有 n 个键值，那么它就有 n + 1 个子节点，所以ptr数组中是从0开始存放关系的。

4.B树的删除逻辑

4.1B树节点的下限

由于B树的所有设计都围绕一个核心：让树尽可能的“矮胖”，而不是“高瘦”。

• 树的高度直接决定了磁盘I/O次数（对于数据库和文件系统至关重要）。一次磁盘I/O可以读取一个完整的节点（页），但非常耗时。树矮意味着从根到叶需要访问的节点数少，I/O次数就少，查询速度就快。

• 节点元素个数的下限和上限（通常称为阶数 m）共同作用来实现这一目标。

在插入操作中我们已经体会过上限的用处了：控制了节点的最大大小，使其与磁盘页对齐，接下来的删除操作我们来体会一下下限的用处。

如果没有下限，可能会出现一种极端情况：一个节点可能只有一个元素，甚至零个元素。这会导致：

• 1.树的高度急剧增加：想象一下，如果每个节点都只有一个元素和两个指针，那么B树就退化成了一个普通的二叉搜索树。失去了“矮胖”的优势，查询效率从 O(log_m n) 退化为 O(log_2 n)，对于海量数据（n很大），log_m n 远比 log_2 n 要小。

• 2.空间浪费：磁盘是按页（如4KB）读取的。如果一个节点只存了很少的数据，那么整个页的大部分空间都被浪费了，磁盘I/O的效率就降低了（传输了多余的空数据）。

而一般：一个 m 阶的B树，其节点（除根节点外）的元素个数 k 必须满足：
下限： ceil(m/2) - 1 <= k
上限： k <= m - 1

例如，一个5阶B树（m=5）：每个节点最多有 4 个元素（m-1）。每个节点（除根节点外）至少有 2 个元素（ceil(5/2) - 1 = 2）。

下限个数这样设计还有个好处就是：

• 当你在一个已满的节点（有 m-1 个元素）中插入新元素时，它才会分裂。

• 分裂后，两个新节点各自大约有 m/2 个元素，都满足下限要求。

• 这个“半满”的状态为新元素的插入提供了空间，确保在下次分裂之前，可以连续进行多次插入，而不是插入一次就分裂一次，提高了插入操作的平均效率。

而为什么根节点不需要满足这个下限条件呢？

因为：为了允许B树从无到有地构建，并保证整个树结构的唯一入口点。这也很好理解，例如：如果根节点也必须满足下限（例如，5阶B树要求至少2个元素），那么这第一个插入操作就是非法的，B树根本无法创建。因此，豁免根节点的下限要求是B树能够开始生长的唯一方式。

4.2B树节点的删除

B-树的删除就复杂的多了，分为下面几种情况：

• 删除叶子节点中的元素：
  1.搜索要删除的元素
  2.如果它在叶子节点上，直接将其删除
  3.如果删除后产生了下溢出（键数小于最小值），则向其兄弟节点借元素。即将其父节点元素下移至当前节点，将兄弟节点中元素上移至父节点（若是左节点，上移最大元素；若是右节点，上移最小元素）
  4.若兄弟节点也达到下限，则合并兄弟节点与分割键。

• 删除内部节点中的元素：
  1.内部节点中元素为其左右子节点的分割值，需要从左子节点最大元素或右子节点中最小元素中选一个新的分割符。被选中的分割符从原子节点中移除，作为新的分隔值替换掉被删除的元素。
  2.上一步中，若左右子节点元素均达到下限，则合并左右子节点
  3. 若删除元素后，其中节点元素小于下限，则继续合并。

我们直接来看一个5阶B树(节点最多4个key，最少2个key)案例：

a) 原始状态

b) 在上面的B树中删除21，删除后结点中的关键字个数仍然大于等2，所以删除结束。

c) 在上述情况下接着删除27。从上图可知27位于非叶子结点中，所以用27的后继替换它。从图中可以看出，27的后继为28，我们用28替换27，然后在原27的右孩子结点中删除28。

删除后发现，当前叶子结点的记录的个数小于2，而它的兄弟结点中有3个记录（当前结点还有一个右兄弟，选择右兄弟就会出现合并结点的情况，不论选哪一个都行，只是最后B树的形态会不一样而已），我们可以从兄弟结点中借取一个key。所以父结点中的28下移，兄弟结点中的26上移,删除结束。

d) 在上述情况下接着删除32。

当删除后，当前结点中只有1个key，而兄弟结点中也仅有2个key。所以只能让父结点中的30下移和这个两个孩子结点中的key合并，成为一个新的结点，当前结点的指针指向父结点。结果如下图所示。当前结点key的个数满足条件，故删除结束。

e) 上述情况下，我们接着删除key为40的记录。

当前结点的记录数小于2，兄弟结点中没有多余key，所以父结点中的key下移，和兄弟（这里我们选择左兄弟，选择右兄弟也可以）结点合并，合并后的指向当前结点的指针就指向了父结点。

对于当前结点而言只能继续合并了，最后结果如下所示。合并后结点当前结点满足条件。

这就是大致流程，接下来我直接把代码发出来供大家参考。

6.B树的代码实现

头文件实现：

#ifndef DISK_BTREE_H
#define DISK_BTREE_H
#define MaxOrder		3			// B树的阶
typedef int KeyType;				// B树节点键值类型

/* B树的阶是MaxOrder（3）,说明最大有3棵子树
 * 在插入节点时，当键值数量为3时，进行分离，申请MaxOrder + 1，从1索引开始填入键值申请的k3
 * 触发节点存放的个数为3，触发分离现象
 * | k0 | k1 | k2 | k3 |		K0无效的，K3是防越界
 * | p0 | p1 | p2 | p3 |
 * p0 < k1,   k1 < p1 < k2，p2 > k2, p3不会访问
 */
// B树的节点结构
typedef struct _BTNode {
    KeyType key[MaxOrder + 1];				// [ 1...MaxOrder -1 ]
    struct _BTNode *ptr[MaxOrder + 1];		// 0开始存放关系
    struct _BTNode *parent;					// 指向父节点
    int keyNum;								// 该节点的键值数量
} BTNode;

// B树头的结构封装
typedef struct {
    BTNode *root;
    int count;
} DiskBTree;

/* B树查找的结果集，包含查找成功和失败
 * ptr : 查找成功，标记为键值所在的节点地址
 *       查找失败，标记待插入节点的父节点地址
 * pos : 查找成功，标记为键值所在的节点的位序索引号
 *       查找失败，标记待插入节点的父节点的位序索引号
 * tag : 1表示查找成功，0表示查找失败
 * */
typedef struct {
    BTNode *ptr;
    int pos;
    int tag;
}Result;

DiskBTree *initDiskBTree();             // 初始化B树
void releaseDiskBTree(DiskBTree *tree); // 释放B树
// 查找B树中key的位置，分查找成功和失败，分别更新res
void searchBTree(const DiskBTree *tree, KeyType key, Result *res);
// 将key值插入到B树
void insertKey(DiskBTree *tree, KeyType key);
// 将key值从B树删除
void deleteKey(DiskBTree *tree, KeyType key);
// 按层次打印B树
void PrintBTree(const BTNode *t, int tab);
// 按关键字大小升序输出B-树关键字
void orderTravelBTree(const DiskBTree *tree);

#endif // DISK_BTREE_H

我来解释一下为什么会有Result结构体，Result结构体用于存储B-树操作（如查找、插入和删除）的结果。它至少包含以下字段，用来表示操作的状态以及相关的节点信息：

• tag: 一个整数标志，用来指示操作是否成功。例如，在查找操作中，如果找到了指定的键值，则tag被设置为1（表示成功），否则设置为0（表示未找到）。
• ptr: 指向BTNode类型的指针，代表与结果相关联的节点。根据不同的情况，这可能是找到的节点、待插入位置的父节点或需要调整的节点等。
• pos: 整数类型，表示在节点内找到或应插入键的位置。

具体来说：

• 当执行searchBTree函数时，如果查找到了给定的键值key，那么res->tag会被设为1，同时res->ptr会指向含有该键值的节点，并且res->pos记录了键值在节点中的位置；如果没有找到，res->tag则为0，而res->ptr将指向最接近目标键值的叶子节点，res->pos表示应该插入新键值的位置。
• 在进行插入或删除操作时，Result同样用于保存过程中产生的中间状态，比如确定了哪个节点需要分裂或者合并，哪些是相关联的兄弟节点等等。

B树的初始化操作：

// ******************** B-Tree的初始化操作 *************************** //
DiskBTree *initDiskBTree() {
	DiskBTree *bTree = malloc(sizeof(DiskBTree));
	bTree->root = NULL;
	bTree->count = 0;
	return bTree;
}

static void destroyBTNode(DiskBTree *tree, BTNode *node) {
	if (node) {
		for (int i = 0; i <= node->keyNum; ++i) {
			if (node->ptr[i]) {
				destroyBTNode(tree, node->ptr[i]);
			}
		}
		free(node);
	}
}

void releaseDiskBTree(DiskBTree *tree) {
	if (tree) {
		destroyBTNode(tree, tree->root);
		free(tree);
	}
}

void PrintBTree(const BTNode *node, int tab) {
	if (node == NULL) {
		return;
	}
	int i;
	for (i = 0; i <= tab; ++i) {
		printf("    ");
	}
	for (i = 1; i <= node->keyNum; i++) {
		printf("%d", node->key[i]);
		if (i != node->keyNum) {
			printf(", ");
		}
	}
	printf("\n");
	for (i = 0; i <= node->keyNum; i++) {
		PrintBTree(node->ptr[i], tab + 1);
	}
}

static void inOrderBTNode(const BTNode *node) {
	if (node) {
		for (int i = 0; i <= node->keyNum; ++i) {
			if (i > 0) {
				printf("%d ", node->key[i]);
			}
			if (node->ptr[i]) {
				inOrderBTNode(node->ptr[i]);
			}
		}
	}
}

void orderTravelBTree(const DiskBTree *tree) {
	if (tree) {
		printf("BTree order: ");
		inOrderBTNode(tree->root);
		printf("\n");
	}
}

查找：

// ******************** B-Tree的查找操作 *************************** //
static int searchNodePos(const BTNode *node, KeyType key) {
	int i = 1;		// 从1号索引开始搜索
	// keyNum描述树阶-1的大小，当该节点找不到满足要求的，i就是最后的占位索引，当i等于3时就退出循环了
	while (i <= node->keyNum && key > node->key[i]) {
		i++;
	}
	return i;
}
void searchBTree(const DiskBTree *tree, KeyType key, Result *res) {
	BTNode *cur = tree->root;		// 定义当前节点的索引
	BTNode *pre = NULL;				// 定义指向前置节点的索引
	int tag = 0;					// 标记成功或失败状态，默认未找到
	int pos = 1;					// 节点中的位序
	while (cur && !tag) {
		pos = searchNodePos(cur, key);
		if (pos <= cur->keyNum && cur->key[pos] == key) {
			tag = 1;
		} else {
			pre = cur;
			cur = pre->ptr[pos - 1];  // 找不到pos就越界，调整到最后一个索引位置
		}
	}
	if (tag) {				// 查找成功，就更新找到的节点信息
		res->tag = 1;
		res->ptr = cur;
		res->pos = pos;
	} else {				// 查找失败，就把待插入节点的父节点信息更新
		res->tag = 0;
		res->ptr = pre;
		res->pos = pos;
	}
}

插入：

// ******************** B-Tree的插入操作 *************************** //
/* 将node节点分裂成两个节点，前一半保留在原节点，后一半移动到other节点
 * 1. 申请新节点，将后半部分信息拷贝到新节点
 *      1.1 中点后一个元素开始拷贝到新节点，中点是为了上移使用
 *      1.2 中点的p是新元素的0位置，从中点后一个元素，逐个更新px
 *      1.3 更新新节点的元素个数，其实是固定数字，阶数 - 中点索引值
 *      1.4 更新新节点的父信息，是原node节点的父亲
 * 2. 新申请节点的子节点的父信息也要更新
 *      2.1 从p0开始，更新到元素个数
 * 此时节点的keyNum正好是maxOrder，而传入的中间索引值也是自然序
 * 那么 n - s 表示的就是从s+1到最后的元素个数
 * */
static void split(BTNode **node, int s, BTNode **other) {
	int i = s + 1;      // 老节点搬移位置
	int j = 1;          // 新节点待放入位置
	int n = (*node)->keyNum;
	BTNode *splitNode = malloc(sizeof(BTNode));
	memset(splitNode, 0, sizeof(BTNode));
	*other = splitNode;
	splitNode->ptr[0] = (*node)->ptr[s];
	for (; i <= n; ++i, ++j) {
		splitNode->key[j] = (*node)->key[i];
		splitNode->ptr[j] = (*node)->ptr[i];
		(*node)->key[i] = 0;
		(*node)->ptr[i] = 0;
	}
	// splitNode->keyNum = n - s;          // n肯定是最大阶数，不然不会split
	splitNode->keyNum = MaxOrder - s;
	splitNode->parent = (*node)->parent;
	for (i = 0; i <= n - s; ++i) {         // n-s的索引是最后一个有效元素的索引
		if (splitNode->ptr[i]) {
			splitNode->ptr[i]->parent = splitNode;
		}
	}
	(*node)->keyNum = s - 1;
}

/* 创建一个根节点，key表示k1，更新2个子节点信息，同时更新p0,p1的父节点 */
static BTNode *createRootNode(KeyType key, BTNode *p0, BTNode *p1) {
	BTNode *node = malloc(sizeof(BTNode));
	memset(node, 0, sizeof(BTNode));
	node->keyNum = 1;
	node->key[1] = key;
	node->ptr[0] = p0;
	node->ptr[1] = p1;
	if (p0) {
		p0->parent = node;
	}
	if (p1) {
		p1->parent = node;
	}
	node->parent = NULL;
	return node;
}

/* 从节点node的pos位序处，插入关键字key，
 * 若是上移键，更新比key大的child子节点索引，即ptr[pos]处更新
 * 在叶子节点插入，child直接为null
 * */
static void insertNode(BTNode *node, int pos, KeyType key, BTNode *child) {
	// 1. 从key表中移动pos及pos后的元素，更新pos位置的值
	int n = node->keyNum;
	for (int i = n; i >= pos; --i) {
		node->key[i + 1] = node->key[i];
		node->ptr[i + 1] = node->ptr[i];
	}
	node->key[pos] = key;
	node->ptr[pos] = child;
	if (child) {
		child->parent = node;
	}
	node->keyNum++;
}

/* 将key插入到B树中的node节点的pos位序处，根据B树规则决定是否分离 */
static void insertBTree(DiskBTree *tree, KeyType key, BTNode *node, int pos) {
	// 在插入键值后，可能满足要求可能不满足要求，也可能需要更新根节点
	int needNewRoot = 0;
	BTNode *child = NULL;
	KeyType x = key;

	if (node) {
		int finish = 0;
		// 有父节点，要么直接插入在父节点，要么进行分离
		while (!finish && !needNewRoot) {
			insertNode(node, pos, x, child);
			if (node->keyNum < MaxOrder) {
				finish = 1;
			} else {		// 已经超过最大有效位置
				int mid = (MaxOrder + 1) / 2;
				split(&node, mid, &child);
				x = node->key[mid];
				if (node->parent) {
					node = node->parent;
					pos = searchNodePos(node, x);
				} else {
					needNewRoot = 1;
				}
			}
		}
	} else {		// 待插入节点的父节点是空，说明产生一个根节点
		tree->root = createRootNode(key, NULL, NULL);
		tree->count = 1;
	}
	if (needNewRoot) {
		tree->root = createRootNode(x, node, child);
	}
}

void insertKey(DiskBTree *tree, KeyType key) {
	Result res;
	// 1. 查找key在B树的待插入位置
	searchBTree(tree, key, &res);
	if (res.tag == 1) {
		printf("键值 %d 已经存在了!\n", key);
	} else {
		insertBTree(tree, key, res.ptr, res.pos);
		tree->count++;
	}
}

删除：

// ******************** B-Tree的删除操作 *************************** //
/* 向兄弟借关键字 */
static void borrowFromBrother(BTNode *node, BTNode *leftBrother, BTNode *rightBrother, BTNode *parent, int pos) {
	if (leftBrother && leftBrother->keyNum >= ((MaxOrder + 1) / 2)) {
		// 左兄弟有富余关键字，向左兄弟借
		for (int j = node->keyNum + 1; j > 0; --j) {
			// 关键字与指针后移，腾出第一个位置
			if (j > 1) {
				node->key[j] = node->key[j - 1];
			}
			node->ptr[j] = node->ptr[j - 1];
		}
		node->ptr[0] = leftBrother->ptr[leftBrother->keyNum];
		if (node->ptr[0]) {
			node->ptr[0]->parent = node;
		}
		leftBrother->ptr[leftBrother->keyNum] = NULL;
		node->key[1] = parent->key[pos];     // 被删节点存父节点关键字
		parent->key[pos] = leftBrother->key[leftBrother->keyNum];   // 父节点的key变为被删除节点左兄弟的最大值
		leftBrother->keyNum--;
		node->keyNum++;
	} else if (rightBrother && rightBrother->keyNum >= ((MaxOrder + 1) / 2)) {
		// 右兄弟有富余关键字
		node->key[node->keyNum + 1] = parent->key[pos + 1];
		node->ptr[node->keyNum + 1] = rightBrother->ptr[0];
		if (node->ptr[node->keyNum + 1]) {
			node->ptr[node->keyNum + 1]->parent = node;
		}
		node->keyNum++;
		parent->key[pos + 1] = rightBrother->key[1];
		for (int j = 0; j < rightBrother->keyNum; ++j) {
			if (j > 0) {
				rightBrother->key[j] = rightBrother->key[j + 1];
			}
			rightBrother->ptr[j] = rightBrother->ptr[j + 1];

		}
		rightBrother->ptr[rightBrother->keyNum] = NULL;
		rightBrother->keyNum--;
	}
}

/* 与左兄弟合并 */
static void mergerWithLeftBrother(BTNode *leftBrother, BTNode *parent, BTNode *node, DiskBTree *tree, int pos) {
	// 与左兄弟合并
	leftBrother->key[leftBrother->keyNum + 1] = parent->key[pos];   // 从父节点拿下分割本节点与左兄弟的关键字
	leftBrother->ptr[leftBrother->keyNum + 1] = node->ptr[0];
	if (leftBrother->ptr[leftBrother->keyNum + 1]) {
		// 给左兄弟的节点，当此结点存在时需要把其父亲指向左节点
		leftBrother->ptr[leftBrother->keyNum + 1]->parent = leftBrother;
	}
	leftBrother->keyNum++;      // 左兄弟关键字加1
	for (int i = 1; i <= node->keyNum; ++i) {
		// 把本节点的关键字和子树指针赋给左兄弟
		leftBrother->key[leftBrother->keyNum + i] = node->key[i];
		leftBrother->ptr[leftBrother->keyNum + i] = node->ptr[i];
		if (leftBrother->ptr[leftBrother->keyNum + i]) {
			leftBrother->ptr[leftBrother->keyNum + i]->parent = leftBrother;
		}
	}
	leftBrother->keyNum += node->keyNum;
	parent->ptr[pos] = NULL;
	free(node);
	for (int j = pos; j < parent->keyNum; ++j) {    // 左移
		parent->key[j] = parent->key[j + 1];
		parent->ptr[j] = parent->ptr[j + 1];
	}
	parent->ptr[parent->keyNum] = NULL;
	parent->keyNum--;       // 父节点关键字个数减1
	if (tree->root == parent) {
		// 如果此时父节点为根，则当父节点没有关键字时才调整
		if (parent->keyNum == 0) {
			for (int i = 0; i <= parent->keyNum + 1; ++i) {
				if (parent->ptr[i]) {
					tree->root = parent->ptr[i];
					tree->root->parent = NULL;
					break;
				}
			}
		}
	} else {
		// 如果父节点不为根，则需要判断是否需要重新调整
		if (parent->keyNum < ((MaxOrder - 1) / 2)) {
			restoreBTree(tree, parent);
		}
	}
}

/* 与右兄弟合并 */
static void mergerWithRightBrother(BTNode *rightBrother, BTNode *parent, BTNode *node, DiskBTree *tree, int pos) {
	for (int i = rightBrother->keyNum; i > 0; --i) {
		if (i > 0) {
			rightBrother->key[i + 1 + node->keyNum] = rightBrother->key[i];
		}
		rightBrother->ptr[i + 1 + node->keyNum] = rightBrother->ptr[i];
	}
	rightBrother->key[node->keyNum + 1] = parent->key[pos + 1];     // 把父节点分割两个本兄弟和右兄弟的关键字拿下来使用
	for (int i = 0; i <= node->keyNum; ++i) {
		// 把本结点的关键字及子树指针移动到右兄弟中去
		if (i > 0) {
			rightBrother->key[i] = node->key[i];
		}
		rightBrother->ptr[i] = node->ptr[i];
		if (rightBrother->ptr[i]) {
			rightBrother->ptr[i]->parent = rightBrother;        // 给右兄弟的节点需要把其父节点指向右兄弟
		}
	}
	rightBrother->keyNum += (node->keyNum + 1);
	parent->ptr[pos] = NULL;
	free(node);
	for (int i = pos; i < parent->keyNum; ++i) {
		if (i > pos) {
			parent->key[i] = parent->key[i + 1];
		}
		parent->ptr[i] = parent->ptr[i + 1];
	}
	if (parent->keyNum == 1) {
		// 如果父结点在关键字减少之前只有一个结点，那么需要把父结点的右孩子赋值给左孩子
		parent->ptr[0] = parent->ptr[1];
	}
	parent->ptr[parent->keyNum] = NULL;
	parent->keyNum--;           // 父节点关键字数减1
	if (tree->root == parent) {
		//如果此时父结点为根，则当父结点没有关键字时才调整
		if (parent->keyNum == 0) {
			for (int i = 0; i <= parent->keyNum; ++i) {
				if (parent->ptr[i]) {
					tree->root = parent->ptr[i];
					break;
				}
			}
			tree->root->parent = NULL;
		}
	} else {
		// 如果父结点不为根，则需要判断是否需要重新调整
		if (parent->keyNum < ((MaxOrder - 1) / 2)) {
			restoreBTree(tree, parent);
		}
	}
}

/* 调整B树，node为需调整的节点 */
static void restoreBTree(DiskBTree *tree, BTNode *node) {
	// 待调整节点的父节点、左右兄弟节点
	BTNode* parent = node->parent;
	if (parent) {
		BTNode *rightBrother;
		BTNode *leftBrother;
		// 寻找左右兄弟
		int i;
		for (i = 0; i <= parent->keyNum; ++i) {
			if (parent->ptr[i] == node) {
				break;
			}
		}
		if (i > 0) {
			leftBrother = parent->ptr[i - 1];
		} else {
			leftBrother = NULL;
		}
		if (i < parent->keyNum) {
			rightBrother = parent->ptr[i + 1];
		} else {
			rightBrother = NULL;
		}
		// 左兄弟或右兄弟有富余的关键字
		if ((leftBrother && leftBrother->keyNum >= (MaxOrder + 1) / 2) ||
			(rightBrother && rightBrother->keyNum >= (MaxOrder + 1) / 2)) {
			borrowFromBrother(node, leftBrother, rightBrother, parent, i);
		} else {
			// 左右兄弟都没有富余的关键字，需要合并
			if (leftBrother) {
				// 与左兄弟合并
				mergerWithLeftBrother(leftBrother, parent, node, tree, i);
			} else {
				// 一定有右兄弟
				mergerWithRightBrother(rightBrother, parent, node, tree, i);
			}
		}
	} else {
		// 根节点，去掉根节点，使树减一层
		BTNode *a;
		for (int j = 0; j <= node->keyNum; ++j) {
			if (node->ptr[j]) {
				a = node;
				node = node->ptr[j];
				a->ptr[j] = NULL;
				free(a);
				break;
			}
		}
		tree->root = node;
		tree->root->parent = NULL;
	}
}

/* 找到node后继节点最小关键字，交换值并更新待删除的key信息 */
static void successor(BTNode **node, int pos) {
	BTNode *leaf = *node;
	if (leaf == NULL) {
		return;
	}
	leaf = leaf->ptr[pos];
	while (leaf->ptr[0]) {
		leaf = leaf->ptr[0];
	}
	(*node)->key[pos] = leaf->key[1];
	(*node) = leaf;
}

/* 从节点node的pos位序中移除关键字key */
static void removeNode(BTNode *node, int pos) {
	for (int i = pos; i < node->keyNum; ++i) {
		node->key[i] = node->key[i + 1];
		node->ptr[i] = node->ptr[i + 1];
	}
	node->keyNum--;
}

/* 从tree中删除目标关键字所在node节点的pos位序上 */
static void deleteBTree(DiskBTree *tree, BTNode *node, int pos) {
	if (node->ptr[pos]) {   // 内部节点，非终端节点
		successor(&node, pos);          // 找到后继节点中最小的关键字替代
		deleteBTree(tree, node, 1);     // 删除最下层非终端节点中的最小关键字
	} else {                // 从node节点中删除pos
		removeNode(node, pos);
		if (node->keyNum < ((MaxOrder - 1) / 2)) {
			restoreBTree(tree, node);       // 调整B树
		}
	}
}

/* 从B-tree树上删除key值 */
void deleteKey(DiskBTree *tree, KeyType key) {
	Result res;
	searchBTree(tree, key, &res);
	if (res.tag) {
		deleteBTree(tree, res.ptr, res.pos);
		tree->count--;
	} else {
		printf("关键字key不在B树上!\n");
	}
}

最后测试一下：

#include <stdio.h>
#include "diskBTree.h"

int main() {
	DiskBTree *bTree = initDiskBTree();

	insertKey(bTree, 8);
	insertKey(bTree, 9);
	insertKey(bTree, 10);
	insertKey(bTree, 11);
	insertKey(bTree, 12);

	PrintBTree(bTree->root, 1);

	releaseDiskBTree(bTree);

	return 0;
}

结果：

D:\work\DataStruct\cmake-build-debug\05_Search\DiskTree.exe
        9, 11
            8
            10
            12

进程已结束，退出代码为 0

大家可以用之前我在《01数据结构-二叉搜索树》中提到的算法动图网址比对一下。

由于工程中基本很少会写B树的代码，考研也很少考到B树的代码，我就不一一讲解了。下一篇博客会用两道考研的例题给大家看一下B树在考研中的考察情况，大概先写这些吧，今天的博客就先写到这，谢谢您的观看。