bbtree：一个声称比跳表快达6.83倍的Rust有序映射，以及评论者的质疑

bbtree是一个Rust有序映射（B树），其作者声称在缓存受限的工作负载上优于跳表和std::collections::BTreeMap，报告在四个生产LSM树中用作内存表时加速1.37-6.83倍，作为内存数据库索引插入快2.22倍，从磁盘内存映射时首次回答快160-2500倍。该帖子出现在Hacker News上，标题为“Bbtree: Fastest Ordered Map”（153分，21条评论），托管在bbtree.xiangpeng.systems，由用户aoli-al提交。

bbtree声称能做什么

核心论点是B树支撑着大多数大数据系统，因此更快的B树能改善所有构建在其上的东西：代理内存、LLM训练、RAG、KV存储、状态缓存和向量搜索。帖子展示了三个代表性用例及基准测试数据。

1. 替换LSM树内存表中的跳表

每个LSM树都将最近的写入以有序映射的形式保存在内存中，称为内存表。在Rust中，该映射通常是跳表，如crossbeam-skiplist。帖子报告bbtree以1.37-6.83倍的速度替换它，这是在每个系统自己的基准测试上测量的，单线程，在Ryzen 9 9900X上，仅更改映射：

  • fjall：获取快2.47倍，插入快1.61倍，写批处理快3.00倍
  • SlateDB：获取快1.71倍，放置快1.65倍，10行写批处理快2.36倍
  • Tonbo：1000万行写入快6.83倍，冲突检查事务快4.10倍
  • Lance的MemWAL索引（其自己的跳表）：点查找快2.19倍，批量查找快3.94倍，批量放置快4.21倍

所述的接口优势是bbtree暴露了类似于crossbeam-skiplist但更简单的API，没有epoch，也无需考虑何时固定或重新进入epoch。内存管理也更可控：从第一天起就支持自定义分配器，分配永远不会在不规则（非2的幂）大小上进行，这避免了外部碎片，并且可以优雅地处理分配失败。

2. 内存数据库索引

替换Turso的跳表，帖子报告插入快2.22倍，索引SELECT快1.90倍。

3. 从磁盘内存映射bbtree

由于bbtree可以直接mmap，重启后无需重建步骤。帖子报告首次回答比使用std的BTreeMap快160-2500倍。

设计背后的成本模型

帖子将所有优化围绕三个成本展开，按优先级排序：

  1. 触及的链式缓存行数量。缓存未命中大约花费100纳秒。
  2. 执行的指令数量。一条指令大约花费0.5纳秒。
  3. 缓存一致性流量，这对并发访问最重要。它强制缓存未命中，成本略高于100纳秒。

由于缓存未命中大约是指令成本的200倍，主要目标是最小化缓存未命中，并且对于每次未命中，尽可能缩小搜索空间。

线性搜索在约16个条目以下优于二分搜索

帖子对一个排序的u64值数组进行了思想实验。二分搜索每次缓存未命中将剩余搜索空间减半。线性搜索每次未命中排除cache_line_size / item_size个条目，对于u64是64 / 8 = 8。因此盈亏平衡点约为16个条目，此时两种策略最多花费两次缓存未命中。两个注意事项将实际盈亏平衡点推高：CPU预取器可能自行获取后续缓存行，有利于线性搜索；线性搜索更简单，允许更多CPU流水线并行。帖子用64个排序的u64值（每缓存行8个）说明：二分搜索需要3次未命中，线性搜索在该大小下需要6次，但在16个条目时两者最多需要2次。

这就是为什么bbtree将节点大小调整为大约16-32个条目，以便始终可以使用线性搜索，这也使SIMD可行。该设计遵循了早期关于缓存感知B+树的工作（Rao和Ross，SIGMOD 2000）。

inline_keys：使堆分配的键缓存友好

字符串键打破了上述算术。String的字节存储在堆上，而不是内联在节点中，因此加载一个键成为其自己的缓存未命中，而不是一次未命中获取8个键。对于String键，二分搜索通常更可取。

bbtree的答案是inline_keys，帖子将其描述为数据库使用了几十年的想法，类似于German字符串和Apache Arrow中的StringView。从每个键派生的固定宽度代码内联存储在节点中。使用固定大小的内联键，一次缓存未命中再次加载8个或更多键，并且仅在比较平局时才加载完整键。

prefix_keys处理长共享前缀

诸如URL和文件路径之类的键通常共享长前缀，因此仅取前8个字节作为内联键可能比较不出有用的内容。bbtree存储一个prefix_keys值：节点中所有键的公共前缀。没有节点需要显式存储这些字节。节点中的每个键在父节点中两侧分隔符之间排序，因此如果这两个分隔符共享前20个字节，则子节点中的每个键都以相同的20个字节开头。因此，每个节点仅存储其前缀的长度，并保留每个键紧随其后的窗口。该技术可追溯到Prefix B-Trees（Bayer和Unterauer，TODS 1977）。

整数键也受益

诸如u64和u128之类的整数键可以使用相同的技巧，前提是它们以大端序存储，以便其字节与数字排序相同。

InlineKey trait和Rust的类型系统

用户可以为自己的键类型（包括复合结构体键）实现InlineKey trait。该trait声明2、4或8的字节宽度，以及一个函数，该函数返回键编码在给定偏移处的8个字节，大端序，超出末尾零填充：

pub trait InlineKey: Ord {
    /// 节点保留的每个内联键的字节数：2、4或8。
    const WIDTH: InlineWidth = InlineWidth::Eight;

    /// 键编码的字节`offset..offset + 8`，大端序，
    /// 超出末尾为零，其排序与键相同。
    fn inline_key_at(&self, offset: usize) -> InlineWord;
}

帖子将Rust的类型系统确定为最棘手的部分。要求每个键类型实现InlineKey会阻止bbtree成为std的BTreeMap和BTreeSet的直接替代品。Nightly Rust具有专门化（RFC 1210，自2016年以来不稳定）正是为此目的。对于稳定版Rust，bbtree手动专门化常见类型：u64、i64、u128、i128、String、str、&str、Vec、&[u8]、Box、Box<[u8]>、[u8; 16]、[u8; 20]和[u8; 32]。因此，内置类型无需额外工作即可优化，而用户类型可以选择加入。

批处理模式：将缓存未命中视为Future

第二类优化是隐藏延迟而不是减少延迟。软件预取有帮助，但对于B树来说还不够，因为B树的内存访问本质上是链式的：在搜索完当前节点之前，无法获取下一个节点。

bbtree利用了B树通常批量读取或构建的事实。批处理API（如get_many_copied和insert_many）接受键数组并返回答案数组。在内部，bbtree将缓存未命中视为Future并等待它，就像Rust代码等待IO操作一样。代码形状大致如下：

fn get_many<const N: usize>(&self, keys: [&K; N]) -> [Option<V>; N] {
    let lanes = keys.map(|key| self.search(key));
    block_on(join_all(lanes))
}

async fn search(&self, key: &K) -> Option<V> {
    let mut node = self.root();
    while node.is_internal() {
        let edge = node.search(key);
        node = node.child(edge);
        prefetch(node.header()).await;
    }
    node.get(key)
}

三个约束塑造了实现。首先，缓存未命中大约花费100纳秒，因此Future必须非常轻量级；像tokio这样的通用运行时在开销上会比缓存未命中本身花费更多，因此bbtree使用自己的微型执行器轮询其通道，该执行器不进行分配且不使用运行时。其次，编译时生成的每函数异步状态机必须尽可能小，以便状态切换廉价。第三，由于无法知道缓存行是否已驻留，bbtree进行猜测：一旦叶子超出L2缓存，叶子几乎总是未命中，而较小的树则一次查找一个键。帖子指出，数据库研究多年来一直以这种方式交错查找，手动和协程方式都有。

正确性

帖子明确指出速度容易而正确性困难：性能是可测量的，LLM可以在工作负载上迭代，但正确性是隐式的，没有提示列出每个DON'T，没有测试套件证明代码正确，也没有人能枚举每个期望的属性。帖子声明bbtree有三个守卫来接近正确性。一位评论者引用了项目自身对该工作的框架：“通过形式验证、模型检查、确定性模拟、模糊测试和大量测试实现生产就绪。”本节引用的参考文献指向Verus（用于验证具有线性幽灵类型的Rust程序）、AWS的Shuttle（用于测试并发Rust代码）和ffs（一种基于fork的确定性并发测试工具）。

声称遭遇反驳之处

Hacker News讨论对“最快”一词明显持怀疑态度，几位评论者提供了反数据。

一个交换后变慢的真实工作负载

评论者virtualritz在3D布尔网格内核中测试了bbtree，仅将std::BTreeMap替换为bbtree，没有其他代码更改，并报告了回退：96到1536个面的网格上的并集和差集操作变慢11%到21%，交集阶段变慢16%到34%。在更大的测试夹具上，一个具有一百万个顶点ID的Nefertiti半身像扫描（最佳3次，秒）：

笼式操作 std bbtree
差集 84.2 83.0
并集 83.2 85.6
交集 61.3 67.1
极限曲面差集（最佳2次） 123.9 147.2

得出的结论是，bbtree的优势可能仅在特定且可能狭窄的用例集下成立，而像std::BTreeMap这样的通用映射必须做出妥协以在任意工作负载下保持性能。

Trie是真正的竞争对手

评论者nicknash认为B树的自然竞争对手是基于trie的结构，包括突发trie、优化的q-fast和p-fast trie、级别压缩trie、分桶trie和路径压缩trie，以及优化的分层树，如van Emde Boas布局（在键长度允许的情况下）。论点是完全基于比较的结构很少是必要的，因为整数、浮点数和字符串可以通过字典序结构处理，并且trie在均匀随机数据上表现特别好，操作时间为log-log级别。该评论者在对这项工作表示赞赏的同时，仍对“最快”标签持怀疑态度。

字符串键上的内存使用

评论者ytxm测量了从String到usize的映射，使用/usr/share/dict/words，值为字典偏移量，并报告bbtree比std::collections::BTreeMap多使用约40%的RAM。他们指出这是一个数据点而不是反驳，因为帖子关于更低内存的声明专门针对整数键。同一位评论者批评了动画网页论文格式，称动态元素需要跳过阅读的内容与阅读的内容一样多。

对框架的怀疑

其他评论质疑了项目的定位。一位评论者引用了“没有人类能写出比LLM更好的代码”并称之为大胆声明；另一位询问模型检查在此上下文中意味着什么；另一位将文章斥为“AI垃圾”并反对开篇引语；还有一位只是要求提供源代码。

从业者的兴趣

并非所有反应都是负面的。评论者elendilm描述使用BTreeMap在其系统Dip的“智能批处理”的分散阶段去重工作，并表示在大多数批量写入工作负载（单个请求中20万+次插入）中，此去重是最慢的阶段，有时占扇出、数据库写入、提交和收集总时间的3倍。他们计划在那里尝试bbtree。评论者jared_hulbert从事相邻问题，强调了帖子对一致性流量的处理，并表示他们打算将自己的技术应用于bbtree。

关键要点

  • bbtree是一个Rust有序映射，作为std::BTreeMap和BTreeSet的直接替代品，也替换LSM树内存表中的跳表。
  • 其头条数字来自四个LSM树集成（每个系统自己的基准测试，最高6.83倍）、内存数据库索引（插入2.22倍，索引SELECT 1.90倍）以及mmap磁盘驻留树（首次回答比std的BTreeMap快160-2500倍）。
  • 该设计围绕缓存未命中通过三种机制组织：16-32条目节点线性搜索、inline_keys（在节点中保留固定宽度键代码）和prefix_keys（仅存储节点键的共享前缀长度）。
  • 批处理API通过将未命中视为可等待的Future并使用专用、无分配的执行器（而非tokio）轮询通道来隐藏缓存未命中延迟。
  • 独立测试报告在3D布尔网格内核上出现回退，在String键映射上内存使用高约40%，因此性能声明似乎依赖于工作负载而非普遍适用。
  • 该帖子在发布前由Andrew Lamb（InfluxData）、Zac Farrell、Eddie Tejeda和Divya Ranganathan（Hotdata）、Jacopo Tagliabue（bauplan）、Wanxiang Zhong和Junxuan Liao审阅。

Sources