b树中的节点会记住搜索期间最近找到的索引，如果下一次搜索恰好是相同的值或非常接近的值，则二分搜索会更快。这仅在时间相关的搜索往往具有附近的键值的情况下有帮助，但这可能非常常见。
点击标题，这是一个B 树的C和Go实现路径优化：使用了一种称之为路径提示的东西。这是一个搜索优化。
路径提示是提供给 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 做了一些类似的事情，它产生了奇迹。