tidwall/btree:B树路径提示可大幅度提升B-Tree搜索性能

21-07-31 banq

b树中的节点会记住搜索期间最近找到的索引,如果下一次搜索恰好是相同的值或非常接近的值,则二分搜索会更快。这仅在时间相关的搜索往往具有附近的键值的情况下有帮助,但这可能非常常见。

点击标题,这是一个B 树的CGo实现路径优化:使用了一种称之为路径提示的东西。这是一个搜索优化。

路径提示是提供给 B 树操作的预定义路径。这只是一个提示,“嘿B-tree,不要从中间索引开始二分搜索,从我提供给你的开始。我的路径可能是错误的,如果是这样,请为我提供正确的路径,以便我下次正确。”

我发现使用路径提示可以使性能提高 150% - 300%。这是因为在现实世界的情况下,我正在处理的项目通常在树中彼此靠近。

主要适合:

  • 插入一组时间序列;
  • 我在表格中间的某处顺序插入一组有序的行;
  • 或者,我有一个 Redis 风格的键/值存储,其中键看起来具有通用结构“user:98512:name”、“user:98512:email”,我想为指定用户更新一堆值。

注意点:

  • 对于单线程程序,可以在程序的生命周期内为每个 B 树使用一个共享路径提示。
  • 对于多线程程序,我发现最好为每个 B-tree 每个线程使用一个路径提示。
  • 对于服务器-客户端程序,每个 B 树、每个客户端一个路径提示就足够了。

 

黑客新闻讨论:

一个类似的想法是手指搜索(https://en.wikipedia.org/wiki/Finger_search),您可以将树的遍历从 O(log(number of items in the tree)) 转换为 O(log(number)手指和键之间的项目))。

一个相关的:指数搜索。它是排序数组等价物;

 

这只是为了解决树顶部缺少有状态迭代器而添加的一个杂项。在这个用例中,作者指出它是关于利用请求路径中的局部性。想象一下,树提供了一个迭代器来维护它的路径堆栈,并且那个东西有一个 seek 方法。您可以优化该内容,以便仅在需要时返回到根目录。有状态迭代器与 btree 很好地配对。

 

C++ STL 有类似的东西,插入操作接受一个迭代器作为提示:

https://en.cppreference.com/w/cpp/container/map/insert

在常见的实现中,迭代器只是节点指针,这就足够了,因为节点有父指针,所以你可以恢复整个路径。

在像有序插入这样的极端情况下,这有效地减少了 log(n) 因素。

  

我不确定这对传统数据库有用。有许多成本比数量级更重要。

这是 CPU 优化,但是在 DB 中的主要成本是 1) 从磁盘中提取块 2) 通过网络传输结果。

即使假设节点缓存在内存中,数据库的 B 树节点也可能适合 L1 缓存。SQLite 页面大小默认为 4098 字节,而 8KB+ L1 缓存大小。如果你有一棵大树,你难道不应该仅仅为了从内存中加载下一个节点而支付 100 倍的成本吗?理论上,总体上的快 <1%。

我很好奇 3 倍的改进是总体上的,还是仅仅来自二分搜索。

 

我想你会发现 splay 树提供了类似的属性,可能以更优雅的方式。

对于我使用过的应用程序,这种技术会导致最热的数据最终被压缩到较少数量的连续存储块中。

这种技术的强大之处在于它在所有访问(读取)中分摊了树的优化,而不仅仅是插入和删除(或其他特殊目的的重新平衡操作)。

 

我喜欢splay树, skew堆等数据结构,但很少有人喜欢。

但我实际上尝试在生产代码中使用splay树。与简单的 Patricia 树相比,性能优势在实际实践中似乎完全不存在,即使对于非常频繁的相邻查询之类的事情也是如此。结构很整洁,但注意内存布局和缓存线大小要重要得多。

 

“路径提示”听起来很像光标。由于很多b-tree遍历是有序的,知道树中的最后一个位置往往是有价值的信息。

  

早在 1990 年代,我用 SQL 做了一些类似的事情,它产生了奇迹。

 

 

猜你喜欢