数据结构中的 B 树：搜索、插入、删除 Opera化示例

B 树规则

以下是创建 B_Tree 的重要规则

• 所有的叶子都将在同一层级上创建。
• B-Tree 由一定数量的度数决定，也称为“顺序”（由外部参与者指定，如程序员），简称

  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-Tree 的原因

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

B 树的历史

• 数据以块的形式存储在磁盘上，这些数据在被带入主存（或 RAM）时被称为数据结构。
• 当数据量巨大时，在磁盘中搜索一条记录需要读取整个磁盘；由于磁盘访问频率高且数据量大，这会增加时间和主内存消耗。
• 为了解决这个问题，创建了索引表，根据记录所在的块保存记录的记录引用。这大大减少了时间和内存消耗。
• 由于我们拥有大量数据，因此我们可以创建多级索引表。
• 可以使用 B 树设计多级索引，以便以自平衡方式保持数据排序。

搜索 OperaTION

查找操作是B Tree上最简单的操作。

应用以下算法：

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

插页 OperaTION

由于 B 树是自平衡树，因此您不能强制将键插入到任何节点中。

应用以下算法：

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

小提示	下列关于插入算法的说法不正确： 由于节点已满，因此会分裂，然后插入新值

在上面的例子中：

• 在节点中适当的位置搜索密钥
• 将密钥插入目标节点，并检查规则
• 插入后，节点是否具有大于等于最小键数（即 1）的键数？在本例中，是的。检查下一条规则。
• 插入后，节点的键数是否超过最大键数（即 3）？在本例中，没有。这意味着 B 树没有违反任何规则，插入已完成。

在上面的例子中：

• 该节点已达到最大密钥数量
• 节点会发生分裂，中间的密钥将成为其余两个节点的根节点。
• 如果键的数量为偶数，则将按左偏向或右偏向选择中间节点。

在上面的例子中：

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

类似地，13 和 2 可以轻松地插入到节点中，因为它们满足节点的少于最大键规则。

在上面的例子中：

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

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

删除 OperaTION

删除操作比插入和搜索操作有更多的规则。

应用以下算法：

• 运行搜索操作并在节点中找到目标键
• 根据目标键的位置应用三个条件，如以下章节所述

如果目标键位于叶节点

• Target 位于叶节点中，超过最小键数。
• 删除这个不会违反B树的性质
• Target 位于叶节点，具有最小关键节点
• 删除此项将违反 B 树的属性
• Target 节点可以从紧邻的左节点或紧邻的右节点（兄弟）借用密钥
• 兄弟姐妹会说 含 如果它有超过最小数量的键
• 从父节点借用密钥，将最大值转移给父节点，将父节点的最大值转移给目标节点，并删除目标值
• Target 位于叶节点，但没有兄弟节点拥有超过最小数量的键
• 搜索密钥
• 与兄弟节点和最小父节点合并
• 现在总密钥数将超过最小值
• 目标键将被替换为父节点的最小值

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

• 选择按顺序的前任或按顺序的后继
• 如果是按序前驱，则将选择其左子树中的最大键
• 对于按顺序后继的情况，将选择其右子树中的最小键
• 如果目标键的按序前驱具有比最小键更多的键，则只有这样它才能用按序前驱的最大值替换目标键
• 如果目标键的按序前驱没有超过最小键，则寻找按序后继的最小键。
• 如果目标键的按序前任和后继都具有少于最小键的键，则合并前任和后继。

如果目标键位于根节点中

• 用中序前驱子树的最大元素替换
• 如果删除后，目标具有的键少于最小值，则目标节点将通过兄弟节点的父节点从其兄弟节点借用最大值。
• 父级的最大值将被目标采用，但会使用兄弟级的最大值的节点。

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

上图显示了 B 树中删除操作的不同情况。此 B 树的阶数为 5，这意味着任何节点可以拥有的最小子节点数为 3，而任何节点可以拥有的最大子节点数为 5。而任何节点可以拥有的最小和最大键数分别为 2 和 4。

在上面的例子中：

• 目标节点有要删除的目标键
• 目标节点的键数超过最小键数
• 只需删除密钥即可

在上面的例子中：

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

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

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

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

• 目标节点将从直属兄弟节点借用一个键，在本例中为按顺序后继节点（右兄弟节点），因为它的按顺序前任节点（左兄弟节点）具有与最小键相等的键。
• 按序后继的最小值会传送给父节点，父节点会将最大值传送给目标节点。

在下面的例子中，目标节点没有任何兄弟节点可以将其密钥提供给目标节点。因此，需要进行合并。

请参阅删除此类键的过程：

• 将目标节点与其任意直系兄弟节点以及父键合并
• 从父节点中选择两个合并节点之间的兄弟节点的键
• 从合并节点中删除目标键

删除 Opera伪代码

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 树的查找操作是最简单的，它总是从根开始，开始检查目标键是否大于或小于节点值。
• B Tree 的插入操作比较详细，首先为目标键找到合适的插入位置，然后插入，评估 B Tree 对不同情况的有效性，然后相应地重组 B Tree 节点。
• B 树的删除操作首先搜索要删除的目标键，然后将其删除，并根据目标节点、兄弟节点和父节点的最小键和最大键等几种情况评估其有效性。