数据结构中的 B 树：查找、插入、删除

⚡ 智能摘要

数据结构中的 B 树是一种自平衡树，它能保持数据有序，从而实现磁盘上的快速搜索、插入和删除操作。本文解释了 B 树的规则、发展历史以及搜索、插入和删除算法，并提供了示例。

🌲 自我平衡： B 型树使所有叶片保持在同一水平线上，并在每次操作过程中保持平衡。
🔢 订单（米）： 度 m 决定了每个节点的最大子节点数 (m) 和键数 (m − 1)。
🔍 使用以下 search 搜索栏来有系统地查看 搜索从根目录开始，通过比较键值向左或向右移动。
➕ 插：插入操作找到正确的位置，并将一个完整的节点与其中间键拆分出来。
➖ 删除： 删除操作会使用借用和合并来处理叶子节点、内部节点和根节点的情况。

什么是 B 树？

B 树 B树是一种自平衡数据结构，它基于一套特定的规则，以更快、更节省内存的方式进行数据搜索、插入和删除。为了实现这一点，创建B树遵循以下规则。

B树是一种特殊的数据结构树。1972年，McCreight和Bayer首次提出了这种方法，并将其命名为高度平衡m路搜索树。它有助于保持数据有序，并能以更短的时间完成插入、搜索和删除等各种操作。

B 树规则

以下是创建 B 树的重要规则：

所有的叶子都将在同一层级上创建。
B树由度数决定，度数也称为“阶”（由外部人员，例如程序员指定），称为 m 价值 m 取决于数据主要位于的磁盘上的块大小。
节点左子树的值将小于子树右侧的值。这意味着节点也是从左到右按升序排列的。
根节点及其子节点可以包含的最大键数由以下公式计算： m − 1。例如：
```
m = 4
max keys: 4 − 1 = 3
```

除了根节点之外，每个节点都必须包含最少数量的键。 [m/2] − 1。例如：
```
m = 4
min keys: 4/2 − 1 = 1
```
一个节点可以拥有的最大子节点数等于该节点的度数，即 m.
一个节点所能拥有的最小子节点数是阶的一半，即m/2（取上限值）。
节点中的所有键均按升序排序。

为什么使用 B-Tree

以下是使用 B 树的原因：

减少磁盘读取次数。
B 树可以很容易地进行优化，根据磁盘大小调整其大小（即子节点的数量）。
它是一种专门为处理大量数据而设计的技术。
它对于数据库和文件系统来说是一个有用的算法。
在读写大量数据时，这是一个不错的选择。

B 树的历史

数据以数据块的形式存储在磁盘上。当这些数据被加载到主内存（或RAM）中时，就称为数据结构。
对于海量数据，在磁盘上查找一条记录需要读取整个磁盘；由于磁盘访问频率高和数据量大，这会增加时间和内存消耗。
为了克服这个问题，我们创建了索引表，用于保存记录在其所在数据块中的引用信息。这大大降低了时间和内存消耗。
由于我们拥有大量数据，因此我们可以创建多级索引表。
可以使用 B 树来设计多级索引。ping 数据以自平衡的方式排序。

搜索 OperaTION

在 B 树上，搜索操作是最简单的操作。应用以下算法：

设要搜索的键（值）为“k”。
从根开始搜索并递归向下遍历。
如果 k 小于根值，则搜索左子树；如果 k 大于根值，则搜索右子树。
如果节点找到了 k，则只需返回该节点。
如果在节点中找不到 k，则向下遍历到具有更大键的子节点。
如果在树中找不到 k，则返回 NULL。

插页 OperaTION

由于 B 树是自平衡树，因此不能强制将键插入任意节点。以下算法适用：

运行搜索操作并找到适当的插入位置。
将新密钥插入到适当的位置，但如果节点已经具有最大数量的密钥：
该节点将与新插入的键一起从中间元素分离。
中间元素将成为另外两个子节点的父元素。
节点必须按升序重新排列键。

💡提示： 以下是不会关于插入算法的说法是正确的：“由于节点已满，因此它会分裂，然后插入新值。” 首先插入键，只有当键的数量超过最大限制时，节点才会分裂。

在上面的例子中：

在节点中查找键的相应位置。
将键插入目标节点，并检查规则。
插入后，节点的键数是否大于或等于最小键数（即 1）？在本例中，是的。请查看下一条规则。
插入后，节点的键数是否超过最大值 3？在本例中，没有超过。这意味着 B 树没有违反任何规则，插入操作完成。

在上面的例子中：

该节点已达到最大键数。
节点将分裂，中间的键将成为其余两个节点的根节点。
如果键的数量为偶数，则通过左偏或右偏选择中间节点。

在上面的例子中：

节点拥有的键数少于最大键数。
1 插入到 3 的旁边，但违反了升序规则。
为了解决这个问题，需要对密钥进行排序。

同样，13 和 2 可以很容易地插入到节点中，因为它们满足节点的“小于最大键数”规则。

在上面的例子中：

该节点具有的键数等于最大键数。
密钥已插入目标节点，但违反了最大密钥数规则。
目标节点被分裂，并且左偏的中间键现在是新子节点的父节点。
新节点按升序排列。

类似地，基于上述规则和情况，其余的值可以轻松地插入到B树中。

删除 OperaTION

删除操作比插入和搜索操作有更多规则。适用以下算法：

运行搜索操作，在节点中查找目标键。
根据目标密钥的位置，应用三种条件，如下文所述。

如果目标键位于叶节点

Target 位于叶节点中的键数超过最小键数。删除此键不会违反 B 树的性质。
Target 它位于叶节点中，且键节点数最少。删除它将违反 B 树的性质。
目标节点可以从其左侧的直接节点或右侧的直接节点（兄弟节点）借用一个键。
兄弟姐妹会说含如果它拥有的密钥数量超过最小值。
从父节点借用键，将最大值传递给父节点，将父节点的最大值传递给目标节点，并移除目标节点的值。
Target 位于叶节点，但没有兄弟节点的键数超过最小值：查找该键，与兄弟节点和父节点的最小值合并，总键数现在将超过最小值，并将目标键替换为父节点的最小值。

如果目标键位于内部节点中

可以选择按顺序执行的前驱操作或按顺序执行的后继操作。
对于中序前驱节点，将选择其左子树中的最大键。
对于中序后继节点，将选择其右子树中的最小键。
只有当目标键的序贯前驱键的数量超过最小键的数量时，才能用序贯前驱键中的最大值替换目标键。
如果目标键的顺序前驱键没有超过最小键数，则查找顺序后继键的最小键。
如果目标键的按序前任和后继都具有少于最小键的键，则合并前任和后继。

如果目标键位于根节点中

替换为中序前驱子树的最大元素。
如果删除后目标节点的键数少于最小键数，则目标节点将通过其兄弟节点的父节点从其兄弟节点借用最大值。
目标节点将取父节点的最大值，但其节点取兄弟节点的最大值。

现在，让我们通过一个例子来理解删除操作。

上图展示了B树中不同删除操作的情况。这棵B树的阶数为5，这意味着任何节点最少可以有3个子节点，最多可以有5个子节点。而任何节点最少可以有2个键，最多可以有4个键。

在上面的例子中：

目标节点拥有要删除的目标键。
目标节点拥有的键数量超过最小键数量要求。
直接删除密钥即可。

在上面的例子中：

目标节点的键值等于最小键值，因此我们不能直接删除它，因为这会违反条件。

现在，下图解释如何删除此键：

目标节点将从其直接兄弟节点（在本例中为左兄弟节点）借用一个键，因为它没有任何中序后继节点（右兄弟节点）。
按顺序前驱节点的最大值将传递给父节点，父节点将最大值传递给目标节点（见下图）。

下面的示例说明如何从有序后继中删除需要值的键。

目标节点将从其直接兄弟节点（在本例中为中序后继节点（右兄弟节点））借用一个键，因为其中序前驱节点（左兄弟节点）的键等于最小键。
按序后继的最小值会传送给父节点，父节点会将最大值传送给目标节点。

在下面的示例中，目标节点没有任何兄弟节点可以将其键传递给目标节点。因此，需要进行合并操作。请参阅删除此类键的步骤：

将目标节点与其任意一个直接同级节点以及父节点键合并。
从位于两个合并节点之间的父节点中选择键。
从合并节点中删除目标键。

删除 Operation Pseudo Code

private int removeBiggestElement()
{
    if (root has no child)
        remove and return the last element
    else {
        answer = subset[childCount-1].removeBiggestElement()
        if (subset[childCount-1].dataCount < MINIMUM)
            fixShort (childCount-1)
        return answer
    }
}

输出： 从 B-Tree 中删除最大的元素。

常见问题

是的。人工智能工具可以生成给定指令的插入、拆分和删除操作的逐步图解或动画。这有助于学习者了解树是如何重新平衡的，但您应该根据 B 树规则验证每一步操作。

B树及其变体为人工智能系统所依赖的大型数据集和向量存储建立索引，从而保证了对训练数据或嵌入的快速查找。数据库（而非模型）使用B树来减少磁盘读取次数。

二叉搜索树节点最多有两个子节点和一个键。B树节点可以容纳多个键和多个子节点。ping 树形结构短小，减少了磁盘读取次数，因此非常适合数据库和文件系统。

每次运行的搜索、插入和删除操作的时间复杂度均为 O(log n)，其中 n 为键的数量。由于每个节点包含多个键，树的深度很浅，因此磁盘访问次数非常少。

数据结构中的 B 树：查找、插入、删除