B 树

B 树是一种专门的 m 路树，可广泛用于磁盘访问。一个 m 阶 B 树最多可以有 m-1 个键和 m 个子节点。使用 B 树的主要原因之一是它能够将大量键存储在单个节点中，并通过保持树的高度相对较小来存储大的键值。

m 阶 B 树包含 M 路树的所有属性。此外，它还包含以下属性。

1. B 树中的每个节点最多有 m 个子节点。
2. B 树中的每个节点（根节点和叶节点除外）至少有 m/2 个子节点。
3. 根节点必须至少有 2 个节点。
4. 所有叶节点必须在同一层。

并非所有节点都必须包含相同数量的子节点，但每个节点必须有 m/2 个节点。

下图显示了一个 4 阶 B 树。

在对 B 树执行某些操作时，B 树的任何属性都可能被违反，例如节点可以拥有的最小子节点数。为了保持 B 树的属性，树可能会分裂或合并。

操作

搜索

B 树中的搜索与二叉搜索树中的搜索相似。例如，如果我们要在以下 B 树中搜索项 49。过程将如下所示：

1. 将项 49 与根节点 78 进行比较。由于 49 < 78，因此移动到其左子树。
2. 由于 40 < 49 < 56，因此遍历 40 的右子树。
3. 49 > 45，向右移动。比较 49。
4. 找到匹配项，返回。

B 树中的搜索取决于树的高度。搜索算法在 B 树中搜索任何元素需要 O(log n) 时间。

插入

插入在叶节点级别进行。为了将项插入 B 树，需要遵循以下算法。

1. 遍历 B 树以查找可以插入节点的合适叶节点。
2. 如果叶节点包含少于 m-1 个键，则按递增顺序插入元素。
3. 否则，如果叶节点包含 m-1 个键，则遵循以下步骤。
• 按元素递增顺序插入新元素。
• 在中间值处将节点分裂成两个节点。
• 将中间元素推到其父节点。
• 如果父节点也包含 m-1 个键，则也按相同步骤将其分裂。

示例

将节点 8 插入下图所示的 5 阶 B 树中。

8 将插入到 5 的右侧，因此插入 8。

该节点现在包含 5 个键，这大于（5-1=4）个键。因此，从中间值 8 分裂该节点，并将其推到父节点，如下图所示。

删除

删除也执行在叶节点。要删除的节点可以是叶节点或内部节点。为了从 B 树中删除节点，需要遵循以下算法。

1. 定位叶节点。
2. 如果叶节点包含超过 m/2 个键，则从节点中删除所需的键。
3. 如果叶节点不包含 m/2 个键，则通过从右侧或左侧兄弟节点获取元素来完成键。
• 如果左侧兄弟节点包含超过 m/2 个元素，则将其最大的元素推到父节点，并将中间元素移到删除键的节点。
• 如果右侧兄弟节点包含超过 m/2 个元素，则将其最小的元素推到父节点，并将中间元素移到删除键的节点。
4. 如果两个兄弟节点都不包含超过 m/2 个元素，则通过合并两个叶节点和父节点的中间元素来创建一个新的叶节点。
5. 如果父节点剩余的节点少于 m/2 个，则也在父节点上应用上述过程。

如果要删除的节点是内部节点，则用其按中序遍历的后继或前驱替换该节点。由于后继或前驱总是位于叶节点上，因此过程将与从叶节点删除节点的过程类似。

示例 1

从下图所示的 5 阶 B 树中删除节点 53。

53 存在于元素 49 的右子节点中。删除它。

现在，57 是节点中唯一剩余的元素，5 阶 B 树中必须存在的最小元素数为 2。它小于该值，其左侧和右侧子树中的元素也不足，因此将其与左侧兄弟节点和父节点的中间元素 49 合并。

最终的 B 树如下图所示。

B 树的应用

B 树用于索引数据，并提供对存储在磁盘上的实际数据的快速访问，因为访问存储在磁盘上的大型数据库中的值是一个非常耗时的过程。

搜索包含 n 个键值的未索引和未排序数据库在最坏情况下需要 O(n) 的运行时间。但是，如果我们使用 B 树来索引该数据库，则在最坏情况下将在 O(log n) 时间内搜索。