B 树的路径提示可以带来 150% – 300% 的性能提升

我在 B 树 C 和 Go 实现中使用了一种我称之为路径提示的东西。这是一个搜索优化。标准 B 树是一种基于有序树的数据结构，将其项存储在节点中。 B 树只有一个根节点，它可能有子节点，而那些子节点也可能有子节点。在 B 树中搜索项目很快。准确地说是 O(log N)。这是因为使用了二进制搜索算法。二分查找的工作原理是首先将根节点最中间索引处的项与目标项进行比较。如果中间项大于目标项，则将节点一分为二并在左侧进行二分查找节点的一部分。如果中间较少，则搜索正确的部分。等等。如果找到目标项目，则搜索停止。如果未找到该项目，则将搜索传递到适当索引处的子节点。当找到项目或没有更多子节点时，此遍历​​终止。每个索引都是项目路径的一个组成部分（或者项目应该存储在哪里，如果它不存在于树中）。以第一个示例图像为例。项目 9 位于路径“1/0”处。项目 16 位于路径“1”。项目 21 位于路径“2/1”处。项目 5 位于路径“0/2”处。路径提示是提供给 B 树操作的预定义路径。这只是一个提示，“嘿B-tree，不要从中间索引开始二分搜索，从我提供给你的开始。我的路径可能是错误的，如果是，请提供正确的路径，以便我下次正确。”

我发现使用路径提示可以使性能提高 150% - 300%。这是因为在现实世界的情况下，我正在处理的项目通常在树中彼此靠近。以插入一组时间序列点为例。它们可能经常被接收为几乎连续的物品的夹头。或者，我在表格中间的某处顺序插入一组有序的行。或者，我有一个 Redis 风格的键/值存储，其中键看起来具有通用结构“user:98512:name”、“user:98512:email”，我想为指定用户更新一堆值。使用路径提示可能有助于避免在这些示例中的每一个中进行不必要的二进制搜索。虽然当路径提示正确时我可能会看到 3 倍的提升，但当路径提示完全错误时，我只会看到大约 5% 的减少。对于单线程程序，可以在程序的生命周期内为每个 B 树使用一个共享路径提示。对于多线程程序，我发现最好为每个 B-tree 每个线程使用一个路径提示。对于服务器-客户端程序，每个 B 树、每个客户端一个路径提示就足够了。