前言
本文为系列文章
前一篇文章为大家介绍了 B树 的基本概念及其插入算法。本文将基于前一篇的内容，为大家介绍插入到 B树 中的数据该怎么读取及遍历，
本文的代码基于前一篇文章的代码，已经实现的功能可能会被省略，只介绍新增的功能。
在本文开始前，再次复习下 B树 的顺序特性：
- 每个 节点 中的 Item 按 Key 有序排列（规则可以是自定义的）。
- 升序排序时，每个 Item 左子树 中的 Item 的 Key 均小于当前 Item 的 Key。
- 升序排序时，每个 Item 右子树 中的 Item 的 Key 均大于当前 Item 的 Key。
理解数据的顺序性对本文的理解至关重要。
查询数据
算法说明
B树 是基于二分查找算法进行设计的，某些资料中你也会看到用 多路搜索树 来归类 B树。
在 B树 中查找数据时，二分体现在两个方面：
具体的查找过程如下：
举例说明：
在下面的 B树 中，查找 Key 为 8 的数据。
代码实现
前一篇文章我们定义了 Items 类，用于存储节点中的数据，并且在一开始就定义了一个二分查找算法，用于在 Items 查找 Item。
前一篇用它来找到合适的插入位置，现在我们用寻找已经存在的数据。
在当前节点找到 Item 时，index 对应的就是 Item 的位置。没找到时则代表下一个子树的索引。
理解代码时请参考下图：
internal class Items
{
public bool TryFindKey(TKey key, out int index)
{
if (_count == 0)
{
index = 0;
return false;
}
// 二分查找
int left = 0;
int right = _count - 1;
while (left itemsCount)
{
foreach (var item in _children[childrenCount - 1].InOrderTraversal())
{
yield return item;
}
}
}
}
BTree 实现了 IEnumerable 接口，以便我们可以使用 foreach 循环来遍历 BTree 中的所有 Item，其代码只要调用 Node 的 InOrderTraversal 方法即可：
public sealed class BTree : IEnumerable
{
public IEnumerator GetEnumerator()
{
foreach (var item in _root!.InOrderTraversal())
{
yield return new KeyValuePair(item.Key, item.Value);
}
}
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
}
Benchmarks
最后，我们来看一下 Degree 对 BTree 的性能的影响。
注意，我们这里只考虑 B树的数据量远大于 Degree 的情况。
我们使用 BenchmarkDotNet 来测试，测试代码如下：
public class BTreeWriteBenchmarks
{
[Params(2, 3, 4, 5, 6)] public int Degree { get; set; }
private HashSet _randomKeys;
[GlobalSetup]
public void Setup()
{
_randomKeys = new HashSet();
var random = new Random();
while (_randomKeys.Count < 1000)
{
_randomKeys.Add(random.Next(0, 100000));
}
}
[Benchmark]
public void WriteSequential()
{
var bTree = new BTree(Degree);
for (var i = 0; i < 1000; i++)
{
bTree.Add(i, i);
}
}
[Benchmark]
public void WriteRandom()
{
var bTree = new BTree(Degree);
foreach (var key in _randomKeys)
{
bTree.Add(key, key);
}
}
}
public class BenchmarkConfig : ManualConfig
{
public BenchmarkConfig()
{
Add(DefaultConfig.Instance);
Add(MemoryDiagnoser.Default);
ArtifactsPath = Path.Combine(AppContext.BaseDirectory, "artifacts", DateTime.Now.ToString("yyyy-mm-dd_hh-MM-ss"));
}
}
new BenchmarkSwitcher(new[]
{
typeof(BTreeReadBenchmarks),
}).Run(args, new BenchmarkConfig());
我们测试了 4 项性能指标，分别是顺序读、随机读、最小值、最大值、遍历，测试结果如下：
可以看到，在相同的数据量下，Degree 越大，性能越好，这是因为 Degree 越大，BTree 的高度越小，所以每次查找的时候，需要遍历的节点越少，性能越好。
但是不是真的 Degree 越大就越好呢，我们再来看下写入性能的测试结果：
public class BTreeWriteBenchmarks
{
[Params(2, 3, 4, 5, 6)] public int Degree { get; set; }
private HashSet _randomKeys;
[GlobalSetup]
public void Setup()
{
_randomKeys = new HashSet();
var random = new Random();
while (_randomKeys.Count < 1000)
{
_randomKeys.Add(random.Next(0, 100000));
}
}
[Benchmark]
public void WriteSequential()
{
var bTree = new BTree(Degree);
for (var i = 0; i < 1000; i++)
{
bTree.Add(i, i);
}
}
[Benchmark]
public void WriteRandom()
{
var bTree = new BTree(Degree);
foreach (var key in _randomKeys)
{
bTree.Add(key, key);
}
}
}
测试结果如下：
可以看到，Degree 越大，写入性能也越好，每个节点的容量够大，需要分裂的次数就变少了。
总结
- B树是一种多路平衡查找树，可以基于二分查找的思路来查询数据。
- B树的数据量远大于 Degree 的情况下，B树的 Degree 越大，读写性能越好。如果是磁盘中的实现，每个节点要考虑到磁盘页的大小，Degree 会有上限。
参考资料
Google 用 Go 实现的内存版 B树 github.com/google/btre…
