前言
本文为系列文章
- B树的定义及数据的插入
- 数据的读取及遍历
- 数据的删除
阅读本文前，建议先复习前两篇文章，以便更好的理解本文。
从删除的数据所在的节点可分为两种情况：
- 从叶子节点删除数据
- 从非叶子节点删除数据
无论从叶子节点还是非叶子节点删除数据时都需要保证B树的特性：非根节点每个节点的 key 数量都在 [t-1, 2t-1] 之间。
借此保证B树的平衡性。
之前介绍的插入数据关注的是这个范围的上限 2t-1，插入时，如果节点的 key 数量大于 2t-1，就需要进行数据的分裂。
而删除数据则关注是下限 t-1，如果节点的 key 数量小于 t-1，就需要进行数据的移动或者合并。
删除数据时，需要考虑的情况比较多，本文会分别讨论这些情况，但一些比较边缘的情况为避免描述过于复杂，不再文中讨论，而是在代码中进行了注释。
因为删除逻辑比较复杂，请结合完整代码进行阅读。
https://github.com/eventhorizon-cli/EventHorizon.BTree/blob/b51881719146a86568669cdc78f8524299bee33d/src/EventHorizon.BTree/BTree.cs#L139
从叶子节点删除数据
如果待删除的数据在叶子节点，且该节点的 Item 数量大于 t-1，那么直接删除该数据即可。
从非叶子节点删除数据
如果待删除的数据在非叶子节点，那么需要先找到该数据的左子节点，然后将左子节点的数据替换到待删除的数据，最后再删除左子节点的数据。
这样能保证被删除数据的节点的 Item 数量不变，保证 B树 有 k 个子节点的非叶子节点拥有 k − 1 个键的特性不受破坏。
提前扩充只有 t-1 的 Item 的节点：维持 B树 平衡的核心算法
在数据插入的时候，为了避免回溯性的节点分裂，我们提前将已满的子节点进行分裂。
同样的在数据删除，不断往下递归查找时，如果遇到只有 t-1 个 Item 的节点，我们也需要提前将其扩充，以避免回溯性的节点处理。
扩充的节点不一定是最后数据所在的节点，只是向下查找过程中遇到的节点。
节点扩充的分为两类，一个是从兄弟节点借用 Item，一个是合并兄弟节点，被借用的兄弟节点需要满足 Item 数量大于 t-1。具体可分为以下三种情况：
从左兄弟节点借用 Item
待扩充节点的左兄弟节点存在且左兄弟节点的 Item 数量 > t-1 时，从左兄弟节点借用 Item 进行扩充。
为了保证 B树 数据的顺序特性：任意 Item 的左子树中的 Key 均小于该 Item 的 Key，右子树中的 Key 均大于该 Item 的 Key。需要交换左兄弟节点的最右边的 Item 和父节点中对应位置的 Item（位于左兄弟节点右侧）。
以下图为例进行说明：
从右兄弟节点借用 Item
待扩充节点的左兄弟节点不存在或者左兄弟节点的 Item 数量 只有 t-1 时，无法外借。但右兄弟节点存在且右兄弟节点的 Item 数量 > t-1 时，从右兄弟节点借用 Item 进行扩充。
以下图为例进行说明：
从兄弟节点进行扩充可以概括为：借用，交换，插入。
与左兄弟节点或者右兄弟节点合并
如果待扩充节点的左兄弟节点和右兄弟节点都不存在或者都只有 t-1 个 Item 时，无法外借。此时需要与左兄弟节点或者右兄弟节点进行合并。
以下图为例进行说明：
最值的删除
之前章节介绍过 B树 最值的查找：
- 最小值：从根节点开始，一直往左子树走，直到叶子节点。
- 最大值：从根节点开始，一直往右子树走，直到叶子节点。
最值的删除就是先找到最值的位置并将其删除，在向下寻找的过程中，需要和普通的数据删除一样，对节点进行扩充或者合并。
代码实现
最值删除是删除的特殊情况，我们定义一个枚举用来区分普通数据的删除，最小值的删除以及最大值的删除，这三种方式只在数据查找的时候有所区分，其他的逻辑都是一样的。
internal enum RemoveType { Item, Min, Max } public sealed class BTree<TKey, TValue> : IEnumerable<KeyValuePair<TKey, TValue?>> { public bool TryRemove([NotNull] TKey key, out TValue? value) { ArgumentNullException.ThrowIfNull(key); return TryRemove(key, RemoveType.Item, out value); } public bool TryRemoveMax(out TValue? value) => TryRemove(default, RemoveType.Max, out value); public bool TryRemoveMin(out TValue? value) => TryRemove(default, RemoveType.Min, out value); private bool TryRemove(TKey? key, RemoveType removeType, out TValue? value) { if (_root == null || _root.IsItemsEmpty) { value = default; return false; } bool removed = _root.TryRemove(key, removeType, out var item); if (_root.IsItemsEmpty && !_root.IsLeaf) { // 根节点原来的两个子节点进行了合并，根节点唯一的元素被移动到了子节点中，需要将合并后的子节点设置为新的根节点 _root = _root.GetChild(0); } if (removed) { _count--; value = item!.Value; return true; } value = default; return removed; } } 主要的逻辑定义在 Node 中，不断向下递归
internal class Node<TKey, TValue> { public bool TryRemove(TKey? key, RemoveType removeType, [MaybeNullWhen(false)] out Item<TKey, TValue?> item) { int index = 0; bool found = false; if (removeType == RemoveType.Max) { if (IsLeaf) { if (_items.Count == 0) { item = default; return false; } // 如果是叶子节点，直接删除最后一个元素，就是删除最大的 Item item = _items.RemoveLast(); return true; } // 当前节点不是叶子节点，需要找到最大的子节点，继续向下查找并删除 index = ItemsCount; } if (removeType == RemoveType.Min) { if (IsLeaf) { if (_items.Count == 0) { item = default; return false; } // 当前节点是叶子节点，直接删除第一个元素，就是删除最小的 Item item = _items.RemoveAt(0); return true; } // 当前节点不是叶子节点，需要找到最小的子节点，继续向下查找并删除 index = 0; } if (removeType == RemoveType.Item) { // 如果没有找到，index 表示的是 key 可能在的子树的索引 found = _items.TryFindKey(key!, out index); if (IsLeaf) { // 如果是叶子节点，能找到就删除，找不到就返回 false，表示删除失败 if (found) { item = _items.RemoveAt(index); return true; } item = default; return false; } } // 如果当前节点的左子节点的 Item 个数小于最小 Item 个数，就需要进行合并或者借元素 // 这个处理对应两种情况： // 1. 要删除的 Item 不在当前节点的子节点中，为避免删除后导致数据所在节点的 Item 个数小于最小 Item 个数，需要先进行合并或者借元素。 // 2. 要删除的 Item 就在当前节点中，为避免删除后导致当前节点的 Item 个数小于最小 Item 个数，需要先从左子节点中借一个 Item 过来，保证当前节点的 Item 数量不变。 // 为此先要保证左子节点被借用后的 Item 个数不小于最小 Item 个数。 if (_children[index].ItemsCount <= _minItems) { return GrowChildrenAndTryRemove(index, key!, removeType, out item); } var child = _children[index]; if (found) { // 如果在当前节点找到了，就删除当前节点的 Item，然后将 左子节点 中的最大的 Item 移动到当前节点中 // 以维持当前节点的 Item 个数不变，保证 B树 有 k 个子节点的非叶子节点拥有 k − 1 个键的特性。 item = _items[index]; child.TryRemove(default!, RemoveType.Max, out var stolenItem); _items[index] = stolenItem; return true; } return child.TryRemove(key!, removeType, out item); } private bool GrowChildrenAndTryRemove( int childIndex, TKey key, RemoveType removeType, [MaybeNullWhen(false)] out Item<TKey, TValue?> item) { if (childIndex > 0 && _children[childIndex - 1].ItemsCount > _minItems) { // 如果左边的子节点存在且左边的子节点的item数量大于最小值，则从左边的子节点借一个item var child = _children[childIndex]; var leftChild = _children[childIndex - 1]; var stolenItem = leftChild._items.RemoveLast(); child._items.InsertAt(0, _items[childIndex - 1]); _items[childIndex - 1] = stolenItem; if (!leftChild.IsLeaf) { // 非叶子节点的子节点需要保证数量比item多1，item数量变了，子节点数量也要变 // 所以需要从左边的子节点中移除最后一个子节点，然后插入到当前子节点的第一个位置 child._children.InsertAt(0, leftChild._children.RemoveLast()); } } else if (childIndex < ChildrenCount - 1 && _children[childIndex + 1].ItemsCount > _minItems) { // 如果右边的子节点存在且右边的子节点的item数量大于最小值，则从右边的子节点借一个item var child = _children[childIndex]; var rightChild = _children[childIndex + 1]; var stolenItem = rightChild._items.RemoveAt(0); child._items.Add(_items[childIndex]); _items[childIndex] = stolenItem; if (!rightChild.IsLeaf) { // 非叶子节点的子节点需要保证数量比item多1，item数量变了，子节点数量也要变 // 所以需要从右边的子节点中移除第一个子节点，然后插入到当前子节点的最后一个位置 child.AddChild(rightChild._children.RemoveAt(0)); } } else { // 如果当前节点左右两边的子节点的item数量都不大于最小值（例如正好等于最小值 t-1 ），则合并当前节点和右边的子节点或者左边的子节点 // 优先和右边的子节点合并，如果右边的子节点不存在，则和左边的子节点合并 if (childIndex >= ItemsCount) { // ItemCount 代表最的子节点的索引，如果 childIndex 大于等于 ItemCount，说明右边的子节点不存在，需要和左边的子节点合并 childIndex--; } var child = _children[childIndex]; var mergeItem = _items.RemoveAt(childIndex); var mergeChild = _children.RemoveAt(childIndex + 1); child._items.Add(mergeItem); child._items.AddRange(mergeChild._items); child._children.AddRange(mergeChild._children); } return TryRemove(key, removeType, out item); } } Benchmarks：与 优先队列 PriorityQueue 的比较
我们实现的 BTree 支持自定义排序规则，也实现最值的删除，意味着可以充当优先队列使用。
我们使用 PriorityQueue 与 BTree 进行性能对比来看看 B树 能否充当优先队列使用。
入队性能
public class BTree_PriorityQueue_EnequeueBenchmarks { [Params(1000, 1_0000, 10_0000)] public int DataSize; [Params(2, 4, 8, 16)] public int Degree; private HashSet<int> _data; [IterationSetup] public void Setup() { var random = new Random(); _data = new HashSet<int>(); while (_data.Count < DataSize) { var value = random.Next(); _data.Add(value); } } [Benchmark] public void BTree_Add() { var btree = new BTree<int, int>(Degree); foreach (var value in _data) { btree.Add(value, value); } } [Benchmark] public void PriorityQueue_Enqueue() { var priorityQueue = new PriorityQueue<int, int>(DataSize); foreach (var value in _data) { priorityQueue.Enqueue(value, value); } } }
出队性能
public class BTree_PriorityQueue_DequeueBenchmarks { [Params(1000, 1_0000, 10_0000)] public int DataSize; [Params(2, 4, 8, 16)] public int Degree; private BTree<int, int> _btree; private PriorityQueue<int, int> _priorityQueue; [IterationSetup] public void Setup() { var random = new Random(); _btree = new BTree<int, int>(Degree); _priorityQueue = new PriorityQueue<int, int>(DataSize); while (_btree.Count < DataSize) { var value = random.Next(); _btree.Add(value, value); _priorityQueue.Enqueue(value, value); } } [Benchmark] public void BTree_Remove() { while (_btree.Count > 0) { _btree.RemoveMin(); } } [Benchmark] public void PriorityQueue_Dequeue() { while (_priorityQueue.Count > 0) { _priorityQueue.Dequeue(); } } }
可以看到，B树 虽然在入队性能上比 PriorityQueue 差。但在数据量和 degree 较大时，出队性能比 PriorityQueue 好，是有能力充当优先队列使用的。
总结
B树 在 degree 较大时，树的高度较低，删除的效率较高，可充当优先队列使用。
B树 的插入，删除，查找都是基于递归的，递归的深度为树的高度。
B树 对数据的查找基于二分查找，时间复杂度为 O(log n)，B树 的插入和删除基于 B树的查找算法，都要找到数据所在的节点，然后在该节点进行插入和删除。因此，B树 的插入和删除的时间复杂度也为 O(log n)。
B树 是对二叉树的一种优化，使得树的高度更低，但是在插入，删除的过程中，需要进行大量的节点分裂，合并，借用，交换等操作，使得算法的复杂度更高。
参考资料
Google 用 Go 实现的内存版 B树 https://github.com/google/btree
