B树(B-tree),也常被记作 B-树,其中“-”不发音。B树的发明者 Rudolf Bayer 和 Edward M. McCreight 并没有给B树中的 B 明确的定义,大家也不必对此纠结太多。
B+树是B树的变体,两者的适用场景是不一样的,以后也会给大家带来B+树的介绍。
本系列将用三篇文章讲解B树的设计理念及如何用 C# 实现一个内存版本的B树:
- B树的定义及数据的插入(本文)
- 数据的读取及遍历
- 数据的删除
完整代码已放至github https://github.com/eventhorizon-cli/EventHorizon.BTree
或者安装 nuget 包进行体验
dotnet add package EventHorizon.BTree
完整代码中包含了debug辅助代码,可以通过调试来了解B树的内部结构。
B树最早被设计出来,并不是作为一个单纯的内存数据结构,而是用作 磁盘存储引擎 的索引实现,以后也会单独写一篇文章来做说明。
本文部分说明引用自PingCAP 的公开ppt 宝宝床边故事集:存储引擎,强烈推荐给各位学习。
部分内容属于个人理解,若有不对之处,欢迎指正。
索引原理
局部性(Locality)
硬件、操作系统等等系统,绝大部分时候,执行一次操作流程 有额外的开销(overhead)。
因此很多部件、模块都设计成:连续执行类似或相同的操作、访问空间相邻的内容时,则将多次操作合并为一次,或多次之间共享上下文信息。这样能极大提升性能。
这种时间、空间上的连续性,叫做局部性。
数据的局部性
我们把数据的连续性及连续区域大小称为 局部性,连续存放的数据越多,局部性越好。
内存存储和磁盘存储
IO的访问性能有两个重要的衡量指标:
- IOPS(Input/Output Operations Per Second): 每秒进行IO读写操作的次数
- IOBW(Input/Output Bandwidth): IO带宽
磁盘的IOPS和IOBW都低于内存,IOPS更为明显。
磁盘IO是以 页(page)为单位进行数据读取的,如果数据的局部性好,只加载一个磁盘页到内存就可以实现一组有序数据的连续访问。如果数据的局部性差,则每读取一次数据都有可能要加载一个磁盘页,性能较差。
当数据局部性差时:
- 需要更频繁地访问磁盘
- IOPS 比 IOBW 先达到上限,性能差
当数据局部性好时:
- IOBW 能达到硬件上限
- IOBW 达到上限是理想的最好性能
磁盘存储适合的索引结构
综上所述,就磁盘存储而言,局部性的好坏对性能影响很大。
有序数组的局部性很好,用二分查找法查询数据的时间复杂度是O(log n)。但插入数据时,时间复杂度就成了O(n)。
二叉平衡树(Self-balancing binary search tree,常见的实现如 AVL树 和 红黑树)用二分查找法查询数据的时间复杂度是O(log n)。插入数据时也是先查询到具体位置,时间复杂度是O(log n)。
但二叉平衡树的局部性很差,这在内存中不是什么问题,因为内存访问随机数据的性能很高,但在磁盘中,不断加载不同的磁盘页,overhead 很高。
数据的局部性越好,读性能更好,但写性能会降低。
数据的局部性越差,读性能会变差,但写性能会更好。
B树则是在这两者之间寻求平衡点:
从有序数组的角度看,我们把大数组分割成了一个个小的有序数组,再用另一种有序结构把小数组组织起来,插入数据时,移动数据量减少并且可控。
从树的角度看,用一个个小的有序数组代替元素作为节点,大大增加了局部性,减少了存储 overhead。
B树简介
定义
B树中的节点分为三种:
- 根节点(root node)
- 内部节点(internal node):存储数据以及指向其子节点的指针。
- 叶子节点(leaf node):叶子节点只存储数据,没有子节点。
B树只有一个节点时,根节点本身就是叶子节点。
节点中每一个数据项(下文用 item 代替)都是一组键值对。item 的数量范围需要预定义,通常有以下两种定义方式:
- 度(degree):通常简写为 t,2t-1 代表 item 数量上限。
- 阶(order):通常简写为 m,m 代表 item 数量上限。
本文用 度(degree)进行描述,一个度是 t(t>=2) 的B树被设计为具有以下属性:
- 每一个节点最多有 2t 个子节点。
- 每一个内部节点最少有 t 个子节点。
- 如果根节点不是叶子节点,那么它至少有两个子节点。
- 有 k 个子节点的非叶子节点拥有 k − 1 个键。
- 所有的叶子节点都在同一层。
这5个属性都是为了维持B树的平衡。其中前4个是在 度 被定义后就可以控制的,而第5个是源于B树新增数据的方式,稍后会做解释。
B树中数据的有序性
- 每个 节点 中的 Item 按 Key 有序排列(规则可以是自定义的)。
- 升序排序时,每个 Item 左子树 中的 Item 的 Key 均小于当前 Item 的 Key。
- 升序排序时,每个 Item 右子树 中的 Item 的 Key 均大于当前 Item 的 Key。
用C#定义数据结构
开始算法讲解前,我们需要先定义下将会用到的数据结构。
虽然代码太多可能影响阅读体验,但考虑到 gayhub 可能访问不稳定,还是尽量贴全了。
下图所示是一个 degree 是 3 的 B树,Key 按升序排序。
internal class Item<TKey, TValue>
{
#region Constructors
public Item(TKey key, TValue? value)
{
Key = key;
Value = value;
}
#endregion
#region Properties
public TKey Key { get; }
public TValue? Value { get; set; }
#endregion
}
定义 Items
和 Children
两个类型分别用于存储 Item
集合和子节点集合。为了简化设计以及减少动态扩容带来的性能损失,作为数据实际容器的数组在第一开始就会按最大的 capacity
进行创建。同时也预先给 Items
和 Children
定义好后面会被用到的基本方法。
internal class Items<TKey, TValue>
{
#region Fields
private readonly Item<TKey, TValue?>?[] _items;
private readonly int _capacity;
private readonly IComparer<TKey> _comparer;
private int _count;
#endregion
#region Constructors
public Items(int capacity, IComparer<TKey> comparer)
{
_capacity = capacity;
_items = new Item<TKey, TValue?>[capacity];
_comparer = comparer;
}
#region Properties
public int Count => _count;
#endregion
#region Indexers
public Item<TKey, TValue?> this[int index]
{
get
{
if (index < 0 || index >= _count)
{
throw new IndexOutOfRangeException();
}
return _items[index]!;
}
set => _items[index] = value;
}
#endregion
#endregion
#region Public Methods
/// <summary>
/// 查找指定的键,并返回它的索引,如果找不到则返回key可以插入的位置
/// </summary>
/// <param name="key">指定的key</param>
/// <param name="index">key的索引或者其可以插入的位置</param>
/// <returns>指定的key是否存在</returns>
public bool TryFindKey(TKey key, out int index)
{
if (_count == 0)
{
index = 0;
return false;
}
// 二分查找
int left = 0;
int right = _count - 1;
while (left <= right)
{
int middle = (left + right) / 2;
var compareResult = _comparer.Compare(key, _items[middle]!.Key);
if (compareResult == 0)
{
index = middle;
return true;
}
if (compareResult < 0)
{
right = middle - 1;
}
else
{
left = middle + 1;
}
}
index = left;
return false;
}
public void InsertAt(int index, Item<TKey, TValue?> item)
{
if (_count == _capacity)
throw new InvalidOperationException("Cannot insert into a full list.");
if (index < _count)
Array.Copy(_items, index, _items, index + 1, _count - index);
_items[index] = item;
_count++;
}
public void Add(Item<TKey, TValue?> item) => InsertAt(_count, item);
public void AddRange(Items<TKey, TValue?> items)
{
if (_count + items.Count > _capacity)
throw new InvalidOperationException("Cannot add items to a full list.");
Array.Copy(items._items, 0, _items, _count, items.Count);
_count += items.Count;
}
public Item<TKey, TValue?> RemoveAt(int index)
{
if (index >= _count)
throw new ArgumentOutOfRangeException(nameof(index));
var item = _items[index];
if (index < _count - 1)
Array.Copy(_items, index + 1, _items, index, _count - index - 1);
_items[_count - 1] = null;
_count--;
return item!;
}
public Item<TKey, TValue?> RemoveLast() => RemoveAt(_count - 1);
public void Truncate(int index)
{
if (index >= _count)
throw new ArgumentOutOfRangeException(nameof(index));
for (int i = index; i < _count; i++)
{
_items[i] = null;
}
_count = index;
}
#endregion
}
internal class Children<TKey, TValue>
{
#region Fields
private readonly Node<TKey, TValue?>?[] _children;
private readonly int _capacity;
private int _count;
#endregion
#region Constructors
public Children(int capacity)
{
_capacity = capacity;
_children = new Node<TKey, TValue?>[_capacity];
}
#endregion
#region Properties
public int Count => _count;
#endregion
#region Indexers
public Node<TKey, TValue?> this[int index]
{
get
{
if (index < 0 || index >= _count)
{
throw new IndexOutOfRangeException();
}
return _children[index]!;
}
}
#endregion
#region Public Methods
public void InsertAt(int index, Node<TKey, TValue?> child)
{
if (_count == _capacity)
throw new InvalidOperationException("Cannot insert into a full list.");
if (index < _count)
Array.Copy(_children, index, _children, index + 1, _count - index);
_children[index] = child;
_count++;
}
public void Add(Node<TKey, TValue?> child) => InsertAt(_count, child);
public void AddRange(Children<TKey, TValue?> children)
{
if (_count + children.Count > _capacity)
throw new InvalidOperationException("Cannot add to a full list.");
Array.Copy(children._children, 0, _children, _count, children.Count);
_count += children.Count;
}
public Node<TKey, TValue?> RemoveAt(int index)
{
if (index >= _count)
throw new ArgumentOutOfRangeException(nameof(index));
var child = _children[index];
if (index < _count - 1)
Array.Copy(_children, index + 1, _children, index, _count - index - 1);
_children[_count - 1] = null;
_count--;
return child!;
}
public Node<TKey, TValue?> RemoveLast() => RemoveAt(_count - 1);
public void Truncate(int index)
{
if (index >= _count)
throw new ArgumentOutOfRangeException(nameof(index));
for (var i = index; i < _count; i++)
_children[i] = null;
_count = index;
}
#endregion
}
用 Node
来表示每个节点,支持传入 Comparer
用于实现自定义的排序方式。
internal class Node<TKey, TValue>
{
#region Fields
private readonly IComparer<TKey> _comparer;
private readonly int _degree;
private readonly int _minItems;
private readonly int _maxItems;
private readonly int _maxChildren;
private readonly Items<TKey, TValue?> _items;
private readonly Children<TKey, TValue?> _children;
#endregion
#region Constructors
public Node(int degree, IComparer<TKey> comparer)
{
_degree = degree;
_comparer = comparer;
_minItems = degree - 1;
_maxItems = 2 * degree - 1;
_maxChildren = 2 * degree;
_items = new Items<TKey, TValue?>(_maxItems, _comparer);
_children = new Children<TKey, TValue?>(_maxChildren);
}
#endregion
#region Properties
public int ItemsCount => _items.Count;
public int ChildrenCount => _children.Count;
public bool IsItemsFull => ItemsCount == _maxItems;
public bool IsItemsEmpty => ItemsCount == 0;
public bool IsLeaf => ChildrenCount == 0;
#endregion
// ...
}
public sealed class BTree<TKey, TValue> : IEnumerable<KeyValuePair<TKey, TValue?>>
{
#region Fields
private readonly int _degree;
private readonly IComparer<TKey> _comparer;
private int _count;
private Node<TKey, TValue?>? _root;
#endregion
#region Constructors
public BTree(int degree) : this(degree, Comparer<TKey>.Default)
{
}
public BTree(int degree, IComparer<TKey> comparer)
{
if (degree < 2)
{
throw new ArgumentOutOfRangeException(nameof(degree), "Degree must be at least 2.");
}
ArgumentNullException.ThrowIfNull(comparer);
_degree = degree;
_comparer = comparer;
}
#endregion
#region Properties
public int Count => _count;
public int Degree => _degree;
public IComparer<TKey> Comparer => _comparer;
#endregion
// ...
}
插入数据的过程
先重复一下上文提到的B树的顺序特性:
- 每个 节点 中的 Item 按 Key 有序排列(规则可以是自定义的)。
- 升序排序时,每个 Item 左子树 中的 Item 的 Key 均小于当前 Item 的 Key。
- 升序排序时,每个 Item 右子树 中的 Item 的 Key 均大于当前 Item 的 Key。
插入数据的过程就是在树中找到合适的位置插入数据,同时保证树的顺序特性不变。
寻找位置的过程是递归的,从根节点开始,如果当前节点是叶子节点,那么就在当前节点中插入数据;如果当前节点不是叶子节点,那么就根据当前节点中的 Item 的 Key 和要插入的数据的 Key 的大小关系,决定是向左子树还是右子树继续寻找合适的位置。
以下面这个图例来说明插入数据的过程:
- 在 根节点 中,借助 二分查找法 找到 5 的位置应该在 3 和 7 之间,因为根节点不是叶子节点,所以不能在根节点直接插入,继续在 Node 2 中寻找合适的位置。Node 2 是 3 的右子树,7 的左子树,其中的 Key 都大于 3,小于 7。
- Node 2 是叶子节点,所以可以在 Node 2 中插入 5。按二分查找法找到 5 的位置应该在 4 和 6 之间,所以插入数据后 Node 2 中的 Item 应该是这样的:
[4, 5, 6]
。
分裂:新节点诞生的唯一方式
上文提到单个节点最多只能有 2t-1 个 Item,如果节点已经满了,还有新 Item 需要插入的话,节点就需要进行分裂。
根节点的分裂
如果根节点满了(Item的数量达到2t-1),有需要插入新 Item 的话,就需要对根节点进行分裂,分裂后的根节点会有两个子节点,分别是原来的根节点和新的节点。
分裂分为以下几个步骤(不一定要按这个顺序):
- 创建一个新的节点,作为新的根节点。
- 将原根节点作为新根节点的第一个子节点。
- 将原根节点中间(索引记为mid)的 Item 移动到新的根节点中,作为新根节点的第一个 Item。
- 创建一个新的节点。
- 将原根节点中间 Item 右边的 Item(mid+1开始)移动到新节点中。
- 将原根节点中间 Item 右边的 子节点(mid+1开始)移动到新节点中。
- 将新节点作为新根节点的第二个子节点。
非根节点的分裂
假设当前节点是父节点的第 k 个子节点,也就是父节点 Items[k](用PItems代指) 的左子节点,或者说是PItems[k-1] 的右子节点。当前节点中所有 Item 的 Key 都在 (PItems[k-1], PItems[k])区间内。
分裂分为以下几个步骤:
- 将中间(索引记为mid)的 Item (记作MItem)提升到父节点中,插入 PItems[k],原来的 PItems[k] 移动至 PItems[k+1],父节点中的 Item 依然保持有序。
- 创建新的节点。
- 将右半部分(mid+1开始)的 Item 移至新节点。
- 将右半部分(mid+1开始)的 子节点 移至新节点。
- 将新的节点 插入父节点的子节点的第 k+1 个位置,也就是作为刚改过位置的 MItem 的右子节点,MItem 的 Key 小于 其右子树中所有 Item,顺序性也不会遭到破坏。
新插入的 Item 会根据 Key 的大小,插入到分裂后的左节点或者右节点中。
下图所示B树 degree 为 3,每个 Node 最多有 5(2*3-1)个 Item,在[4,5,6,8,9]
所在节点插入 7 需先进行分裂。6 将被提升到根节点中,原来的 6 所在节点将被分裂成两个节点,7 会被插入到右侧的新节点中。
分裂导致树的高度增加
节点在分裂的时候,如果父节点已经满了,那么父节点也需要分裂,这样就会导致父节点的父节点也需要分裂,以此类推,直到根节点。
而根节点的分裂,会导致树的高度增加。
新 Item 的插入是发生在叶子节点的,分裂也是从叶子节点开始。如果一个节点一开始是叶子节点,随着数据的增加,它始终都是叶子节点,叶子节点分裂后,新的叶子节点也是同一高度的。
这其实解答了上文提到的问题:为什么B树的叶子节点都在同一层。
提前分裂
B树中数据的插入过程,是一个从根节点不断 向下 寻找合适叶子节点的过程。
而分裂是一个从叶子节点不断 向上 的过程。
因此分裂算法的实际实现中,为了避免回溯性分裂(磁盘存储中,回溯带来的 overhead 很大),一般会在 向下 寻找的过程中提前去分裂已经满了的节点。
插入算法实现
在插入新 Item 的过程中,BTree 本质上只是一个入口,大部分的逻辑都是和 节点 相关的,因此我们会把主要的逻辑定义在 节点 中。
Key 已存在时的处理策略
新插入的 Item 的 Key 可能已经存在了,针对已经存在的 Key 的处理方式,这边参考 Dictionary 的处理方式:
- 通过 Indexer 插入数据时新 Value 覆盖旧 Value。
- 通过 Add 插入数据时扔出异常。
- 通过 TryAdd 插入数据时不作任何处理。
对应枚举如下:
internal enum InsertionBehavior
{
/// <summary>
/// 默认操作,如果 key 已经存在,则不会更新 value
/// </summary>
None = 0,
/// <summary>
/// 如果 key 已经存在,则更新 value
/// </summary>
OverwriteExisting = 1,
/// <summary>
/// 如果 key 已经存在,则抛出异常
/// </summary>
ThrowOnExisting = 2
}
并定义对应的处理结果枚举
internal enum InsertionResult
{
None = 0,
Added = 1,
Updated = 2,
}
public sealed class BTree<TKey, TValue> : IEnumerable<KeyValuePair<TKey, TValue?>>
{
#region Indexers
public TValue? this[[NotNull] TKey key]
{
get
{
if (TryGetValue(key, out var value))
{
return value;
}
throw new KeyNotFoundException();
}
set => TryInsert(key, value, InsertionBehavior.OverwriteExisting);
}
#endregion
#region Public Methods
/// <summary>
/// 往B树中添加一个键值对
/// </summary>
/// <param name="key">要添加的元素的key</param>
/// <param name="value">要添加的元素的value</param>
/// <exception cref="ArgumentNullException">key是null</exception>
/// <exception cref="ArgumentException">key已经存在</exception>
public void Add([NotNull] TKey key, TValue? value) =>
TryInsert(key, value, InsertionBehavior.ThrowOnExisting);
/// <summary>
/// 尝试往B树中添加一个键值对
/// </summary>
/// <param name="key">要添加的元素的key</param>
/// <param name="value">要添加的元素的value</param>
/// <returns>true:添加成功;false:添加失败</returns>
public bool TryAdd([NotNull] TKey key, TValue? value) =>
TryInsert(key, value, InsertionBehavior.None);
#endregion
}
插入算法
在 Node 中 定义分裂和判断是否要提前分裂的方法
internal class Node<TKey, TValue>
{
/// <summary>
/// 将当前<see cref="Node{TKey,TValue}"/>分裂成两个<see cref="Node{TKey,TValue}"/>。
/// </summary>
/// <returns>中间位置的<see cref="Item{TKey,TValue}"/>和分裂后的第二个<see cref="Node{TKey,TValue}"/></returns>
public (Item<TKey, TValue?> MiddleItem, Node<TKey, TValue?> SecnodNode) Split()
{
int middleIndex = ItemsCount / 2;
var middleItem = _items[middleIndex];
var secondNode = new Node<TKey, TValue?>(_degree, _comparer);
// 将中间位置后的所有Item移动到新的Node中
for (int i = middleIndex + 1; i < ItemsCount; i++)
{
secondNode._items.Add(_items[i]);
}
_items.Truncate(middleIndex);
if (!IsLeaf)
{
// 将中间位置后的所有子节点移动到新的Node中
for (int i = middleIndex + 1; i < ChildrenCount; i++)
{
secondNode._children.Add(_children[i]);
}
_children.Truncate(middleIndex + 1);
}
return (middleItem, secondNode);
}
/// <summary>
/// 如果指定的子节点已满,则将其分裂为两个子节点,并将中间的 <see cref="Item{TKey,TValue}"/>> 插入到当前节点中。
/// </summary>
/// <param name="childIndex">指定的子节点的索引</param>
/// <returns>True 表示已经分裂了子节点,False 表示没有分裂子节点</returns>
private bool MaybeSplitChildren(int childIndex)
{
var childNode = _children[childIndex];
if (childNode.IsItemsFull)
{
var (middleItem, secondNode) = childNode.Split();
_items.InsertAt(childIndex, middleItem);
// 将新node插入到当前node的children中
_children.InsertAt(childIndex + 1, secondNode);
return true;
}
return false;
}
}
在 BTree 中定义插入方法
public sealed class BTree<TKey, TValue>
private bool TryInsert([NotNull] TKey key, TValue? value, InsertionBehavior behavior)
{
ArgumentNullException.ThrowIfNull(key);
if (_root == null)
{
_root = new Node<TKey, TValue?>(_degree, _comparer);
_root.Add(new Item<TKey, TValue?>(key, value));
_count++;
return true;
}
if (_root.IsItemsFull)
{
// 根节点已满,需要分裂
var (middleItem, secondNode) = _root.Split();
var oldRoot = _root;
_root = new Node<TKey, TValue?>(_degree, _comparer);
// 将原来根节点中间的元素添加到新的根节点
_root.Add(middleItem);
// 将原来根节点分裂出来的节点添加到新的根节点
_root.AddChild(oldRoot);
_root.AddChild(secondNode);
}
// 从根节点开始插入,如果插入的 Key 已经存在,会按照 behavior 的值进行处理
var insertionResult = _root.TryInsert(key, value, behavior);
if (insertionResult == InsertionResult.Added) _count++;
return insertionResult != InsertionResult.None;
}
}
在 Node 中定义插入方法,递归调用直至找到叶子节点,然后在叶子节点中插入
internal class Node<TKey, TValue>
{
public InsertionResult TryInsert(TKey key, TValue? value, InsertionBehavior behavior)
{
// 如果当前key已经存在, 根据插入行为决定是否替换
if (_items.TryFindKey(key, out int index))
{
switch (behavior)
{
case InsertionBehavior.OverwriteExisting:
_items[index].Value = value;
return InsertionResult.Updated;
case InsertionBehavior.ThrowOnExisting:
throw new ArgumentException($"An item with the same key has already been added. Key: {key}");
default:
return InsertionResult.None;
}
}
// 如果当前节点是叶子节点,则直接插入
if (IsLeaf)
{
// index 是新的 item 应该插入的位置,items 按顺序排列
_items.InsertAt(index, new Item<TKey, TValue?>(key, value));
return InsertionResult.Added;
}
// 如果当前节点的子节点已经满了,则需要分裂
// 如果当前节点的子节点没有满,则不需要分裂
// 如果当前节点的子节点分裂了,则需要判断当前key是否大于分裂后的中间key
// 如果当前key大于分裂后的中间key,则需要向右边的子节点插入
// 如果当前key小于分裂后的中间key,则需要向左边的子节点插入
// index 是新的 item 应该插入的位置,如果当做children的索引,则代表应该插入的位置的右边的子节点
if (MaybeSplitChildren(index))
{
// rightmostItem 是子节点分裂后的中间的 item,被提升到当前节点的 items 中的最后一个位置了
var middleItemOfChild = _items[index];
switch (_comparer.Compare(key, middleItemOfChild.Key))
{
case > 0:
// 如果当前key大于分裂后的中间key,则需要向右边的子节点插入
index++;
break;
case < 0:
// 如果当前key小于分裂后的中间key,则需要向左边的子节点插入
break;
default:
// 如果当前key等于分裂后的中间key,根据插入行为决定是否替换
switch (behavior)
{
case InsertionBehavior.OverwriteExisting:
middleItemOfChild.Value = value;
return InsertionResult.Updated;
case InsertionBehavior.ThrowOnExisting:
throw new ArgumentException(
$"An item with the same key has already been added. Key: {key}");
default:
return InsertionResult.None;
}
}
}
// 往子节点插入
return _children[index].TryInsert(key, value, behavior);
}
}
总结
B树中的数据是按照顺序存储的,所以可以使用二分查找法来查找数据,时间复杂度为 O(log n)。
往B树插入数据的过程是一个寻找合适的叶子节点的过程,然后在叶子节点中插入数据,时间复杂度为 O(log n)。
B树的节点中存储的数据量是有限的,所以在插入数据时,可能会发生节点分裂,这样就会导致树的高度增加,所以在插入数据时,需要判断是否需要分裂,如果需要分裂,就需要将中间的数据提升到父节点中,以此类推,直到根节点,如果根节点也需要分裂,就需要新建一个根节点,然后将原来的根节点和分裂出来的节点作为新的根节点的子节点。
参考资料
渴望力量系列 《算法导论第三版》
欢迎关注个人微信公众号 EventHorizonCLI ,最新的原创技术文章将在优先这里发布。