B VS 树搜索程序，插入和删除操作

B树是一种自调整多路径搜索树，可以保持数据有序。它允许在 O(log n) 时间复杂度内完成搜索、插入和删除。当描述B树时，我们需要指定它的顺序。顺序表示节点拥有的子节点的最大数量。一般情况下，字母m用来表示顺序。当m取2时，这就是我们常用的二叉搜索树。

B-tree具有以下特点：

• B-tree中的每个节点至少有两个子节点，最多有2个*阶的子节点。
• B 树中从根节点到叶子节点的所有路径长度相同或差值不超过 1。
• B 树中每个非终端节点至少有 [Math.ceil (order/2)-1] 子节点。
• 搜索、插入和删除B树的时间复杂度为O(h)，其中h是B树的高度。由于B树的高度与logN节点的数量成正比，因此B树的时间复杂度为O(logN)。
• B树中存储的节点数量在每个节点级别至少增加一倍，因此随着高度的每次增加，B树中的节点数量至少增加一倍。所以B树的高度与logN成正比。
• B-tree支持范围查询，可以在O(logN + M)时间内返回数​​据值在[a, b]之间的所有节点，其中M是查询结果中的节点数量。

B 树的优点：

• 由于每个节点可以有多个子节点，因此 B 树的高度较小，使得搜索效率更高。
• B树的节点数至少是阶数的一半，这使得B树非常稳定。即使经过大量的插入和删除操作，B树的高度也不会变得太高或太低。
• 由于每个节点包含更多元素，因此 B 树中较少的节点可以包含大量数据。这使得 B 树成为管理大量数据的理想选择。 B树是许多数据库系统中最常用的索引结构，因为它可以在保持顺序的同时执行高效的插入、删除和搜索操作。

B 树操作

1. B 树搜索过程

B 树搜索操作

B 树搜索过程与二叉搜索树类似。我们总是将指针向下移动到子节点，直到到达叶节点。

例如，搜索节点号。 0005。查找过程大致如下：

• 首先得到根节点[0004和0008]，并与0005进行比较。由于0005大于0004且小于0008，所以必须继续查找右边的节点0004的子树（二分规则，左小右大，小于该节点当前值的子节点放在左边，大于该节点当前值的子节点放在右边）；
• 比较节点0005和节点0006。比较时，因为0005小于0006，所以应该搜索0006左边的树；
• 比较节点0005和节点0005，它们完全相同，找到目标节点。

B树平衡是通过分裂节点来实现的。如果在执行插入或删除操作后，某个节点的子节点数量小于阶数的一半或大于阶数，则必须对节点进行分裂或合并，以维持 B 树的平衡。这种调整称为树调整。重组。

B树插入操作

插入操作首先要找到要插入的新key的插入位置。找到插入位置后，应执行以下步骤：

1. 如果该节点的子节点数量小于顺序，则将新密钥直接插入到该节点中。
2. 否则，需要将节点拆分为两个节点，并从中间拆分键值。新的key被插入到相应的节点中。
3. 在步骤1或2中，如果新节点的父节点的子节点数达到最大值，则必须继续分裂到根节点。
4. 在步骤3中，如果根节点的子节点也达到了最大值，则需要创建一个新的根节点，并分裂原根节点，并在新的根节点中插入新的key。

B树删除操作

删除操作也需要先找到要删除的key的位置。删除操作可以分为三种情况：

• 删除的节点是叶子节点：直接删除key即可。
• 删除的节点有子节点：用子节点替换该节点。
• 删除的节点有两个子节点：用后继或前驱替换该节点。下一个节点是节点中键值大于该节点键值的最小节点。前驱节点是键值最大且小于本节点键值的节点。

合并B树节点的操作如下：

• 如果一个节点的子节点数量小于顺序的一半，则应与其相邻的相关节点合并。
• 将一个节点与其相邻的兄弟节点之一合并，兄弟节点的子节点成为合并节点的子节点。
• 合并节点的父节点的子节点数量减1。如果父节点的子节点数量小于顺序的一半，则必须继续向上合并。
• 与根节点合并时，如果根节点只剩下一个子节点，则必须将整个B树的高度降低一级，即删除根节点，将其唯一的子节点改为新的根节点。

最后我们看一下文中B树特性中字体红色部分：B树中每个无限节点至少有[Math.ceil(order/2)- 1] 子节点，那为什么会这样呢？