bbtree: fastest ordered map

📝 摘要 #

bbtree 是 Rust 标准库 BTreeMap / BTreeSet 的 drop-in 替代实现，作者用一个极简成本模型——链式 cache miss（约 100 ns）≫ 指令（约 0.5 ns）≳ 缓存一致性流量（略高于 100 ns）——把 B 树优化收敛成三件事：让每一次 cache miss 排除尽可能多的搜索空间、减少指令数、减少跨核一致性流量。在四个 LSM-tree（fjall / SlateDB / Tonbo / Lance）的 memtable 中替换 crossbeam skiplist，单线程下 lookup / insert / write-batch 快 1.37–6.83×；内存数据库索引（Turso）insert 快 2.22×、带索引 SELECT 快 1.90×；从磁盘 mmap 一棵大树无需重建，首个答案快 160–2,500×。

核心概念： B 树的性能几乎等价于「一次查找触碰了多少条链式 cache line」。节点大小（16–32 项，从而可以线性搜索、用上 SIMD）与键在节点里的编码方式（inline_keys / prefix_keys）共同决定这个数字；对于无法避免的内存访问，再用 batch + 协程把多次 miss 的延迟重叠掉。

关键技术栈 / 关键要点：

1. 成本模型三原则 — 先数链式 cache line，再数指令，最后数缓存一致性流量。结论是最该做的是「让每次 miss 缩小尽可能多的搜索空间」，这也解释了为什么 skiplist（下行几乎每个节点都 miss）在今天的内存层级上是劣势结构。
2. 二分 vs 线性搜索的临界点 — 一条 64 B cache line 装 8 个 u64：线性搜索每次 miss 排除 8 项，二分每次排除一半，理论打平点约 16 项；预取器和更简单的流水线（更多指令级并行）让实际临界点更高，因此节点装 16–32 项、用线性搜索是合理设计。
3. String 键改变整个方程 — String 的字节在堆上，节点里只存 ptr/len/cap，每次比较都要跟一次指针、每个键各自一次 cache miss，所以字符串键通常应二分。bbtree 用 inline_keys（每键内联 2/4/8 字节）把 8+ 个键压进一条 cache line，只有比较打平（tie）时才真正读堆——与 German strings、Arrow StringView 同源，是数据库用了几十年的手法。
4. prefix_keys 解决长公共前缀 — 节点内所有键都落在父节点两个分隔键之间，所以父节点两个分隔键的公共前缀就是该节点所有键的公共前缀；节点只存前缀长度（内容不存），inline key 的窗口从前缀之后开始取，URL / 文件路径这类长前缀键因此重新变得可区分。
5. 类型系统上做到零成本 — InlineKey trait（WIDTH + inline_key_at）让复合键也能内联，整数需大端编码使字节序 = 数值序。Nightly 用 specialization，stable 上手工 specialize 常见类型（u64/i64/u128/i128/String/str/&str/Vec<u8>/&[u8]/Box<str>/Box<[u8]>/[u8; 16|20|32]），因此内置类型自动变快，同时仍保持 drop-in。
6. 实测 cache line 数（10M 条目、单线程） — u64 10.1 → 4.0（−60.4%）、32 字节 hash 13.9 → 4.7（−66.2%）、JSON 键 45.2 → 6.9（−84.7%）、Wikipedia 标题 45.1 → 13.8（−69.4%）。
7. batch 模式把 cache miss 当成 Future — B 树访存天然串行（不搜完当前节点就不知道下一个节点是谁），但 get_many / insert_many 可以对多个键并发发起预取。bbtree 自带一个不分配、无 runtime 的极小 executor（tokio 之流的开销已超过一次 cache miss），靠编译器生成的小状态机轮转；由于无法查询「某行是否已在缓存」，它的启发式是：叶子超出 L2 后几乎必然 miss，更小的树则逐键查找。
8. 正确性靠人而非提示词 — 代码全部由 LLM 编写，但每个设计决策由 Xiangpeng 把关并承担责任（博士期间写过多个 B 树，含微软生产环境的 Bf-Tree）。性能可度量、可迭代，正确性不可枚举，所以真正的护栏是把注意力押在一位长期泡在 B 树里的人身上。

关键结论 / 实践建议： 数据结构优化的现代主线已经不是「算法复杂度」而是「内存层级」：先按 cache line 重新设计节点布局（容量、线性搜索、内联键、前缀压缩），再用批处理与协程把无法消除的 miss 重叠起来；同时记住键的类型（定长整数 vs 堆上字符串）会彻底改变最优搜索策略。

🧭 原理图 #

图 1：一次查找 = 若干次链式 cache miss（对比 skiplist 每次下行几乎必 miss）

flowchart TD
    Q["lookup(key)"] --> R["根节点<br/>16–32 个分隔键 + 子指针"]
    R -->|"第 1 次 cache miss"| I["内部节点<br/>16–32 个分隔键 + 子指针"]
    I -->|"第 2 次 cache miss"| L["叶子<br/>inline key 数组 + 值"]
    L -->|"仅当 inline key 全部打平（tie）才跟踪指针"| H["堆 heap<br/>完整键字节"]
    L --> A["返回 value"]
    R -.->|"每一次下行"| N["成本模型：一次 miss ≈ 100ns，一条指令 ≈ 0.5ns<br/>→ 每条 cache line 要装下尽可能多的可比较信息"]

图 2：String 节点 vs inline key + prefix key 的字节布局

flowchart TB
    subgraph S1["① 朴素 String 节点：每次比较 = 1 次堆读"]
        direction LR
        A1["ptr · len · cap<br/>24B"] --> H1["堆：Ada_Lovelace"]
        A2["ptr · len · cap<br/>24B"] --> H2["堆：Alan_Turing"]
        A3["ptr · len · cap<br/>24B"] --> H3["堆：Barbara_Liskov"]
    end
    subgraph S2["② inline key + prefix key：一条 cache line 比较全部键"]
        direction LR
        P["prefix_len = 20<br/>内容不存，由父节点两个分隔键推导"] --> K["8 个 8B inline key（共 64B = 1 条 cache line）<br/>Afghanis / Alabama· / Alaska·· / …"]
        K -->|"只有一个键打平"| H4["堆：List_of_bridges_in_Afghanistan<br/>（1 次堆读）"]
    end

图 3：batch 模式把 cache miss 当作 Future 来 await（单线程内交错）

sequenceDiagram
    autonumber
    participant Ex as 单线程极小 executor
    participant T as 一个键的查找任务
    participant M as 内存 / L3

    Ex->>T: poll（任务 1）
    T->>M: 读当前节点分隔键，选定子节点
    T->>M: 预取下一节点后 yield
    Note over Ex: 任务 1 的 cache line 正在路上
    Ex->>T: poll（任务 2 / 3 / 4）… 同样预取后 yield
    M-->>T: 任务 1 的 cache line 到达
    Ex->>T: 恢复任务 1，读已到达的行，继续下行
    Note over Ex,M: 最多约 3 条 line 同时在途，把 100ns 延迟重叠掉

What can it do? #

B-trees are the most important data structure in big data systems, a fast b-tree like bbtree benefits everything on top of it: agents memory, LLM training, RAG, KV store, state caching, vector search, and more.

Here we discuss three representative use cases:

1. Replace skiplist in LSM-trees. In place of the skiplist of four LSM-trees, bbtree is 1.37–6.83× faster.
2. In-memory database index. In place of Turso's skiplists, inserts are 2.22× and indexed SELECT s 1.90× faster.
3. Mmap a bbtree from disk. No rebuild after a restart: the first answer comes 160–2,500× sooner than std's BTreeMap.

All LSM-trees use an ordered map to hold recent writes in memory, the memtable. In Rust, this ordered map is usually a skiplist, like crossbeam-skiplist.

bbtree can easily replace it and is much faster. A skiplist takes a cache miss for almost every node it visits on its way down; a bbtree lookup touches a handful of cache lines (see How it works, below).

bbtree has a similar interface as crossbeam-skiplist but simpler: there is no epoch, no need to worry about when to pin or re-enter an epoch.

bbtree allows more advanced memory management:

1. Custom allocator is supported on day one.
2. It never allocates on irregular sizes (i.e., not a power of two): memory management stays easy, with no external fragmentation ^[1].
3. Allocation failure can be gracefully handled.

We integrated bbtree into four LSM-trees, on each system's own benchmarks:

1. fjall: gets 2.47×, inserts 1.61×, write batches 3.00×.
2. SlateDB: gets 1.71×, puts 1.65×, write batches of 10 rows 2.36×.
3. Tonbo: 10M-row writes 6.83×, conflict-checked transactions 4.10×.
4. Lance 's MemWAL index (its own skiplist): point lookups 2.19×, batched lookups 3.94×, batched puts 4.21×.

The LSM-trees of the End to End card: each system's own benchmark, one thread, Ryzen 9 9900X. The dark bar is the time per operation as shipped, the bright one inside it with bbtree; only the map changed.

How it works? #

Every performance optimization should be guided by a cost model.

B-tree optimizations are simple, three easy pieces ^[2]: we just need to remember three principles, in order:

1. The number of chained cache lines touched. A cache miss costs about 100 ns.
2. The number of instructions executed. An instruction costs about 0.5 ns.
3. The amount of cache coherence traffic, especially important for concurrent access. It forces a cache miss, and costs a little more than 100 ns.

With this cost model, it's clear that the most important optimization is to minimize the number of cache misses. To put it another way, for each cache miss, we want to narrow down the search space as much as we can.

Thought experiment: binary search vs linear search #

Say we have a sorted array of u64 s, and we want to find a target u64.

With binary search, each cache miss narrows down the search space by half.

With linear search, each cache miss narrows down the search space by cache_line_size / item_size items, which is 64 / 8 = 8.

So the break-even point is about 16 items, where binary search costs the same as linear search: two cache misses to find the target.

But there's a catch: 1. the CPU prefetcher may fetch the next cache lines on its own, which gives linear search an even bigger advantage; 2. linear search is simpler, allowing much more parallelism in the CPU pipeline. So the actual break-even point is usually higher.

64 sorted u64 s, 8 to a cache line. Each step is one cache miss: binary search halves what is left, linear search rules out one line. Here binary search needs 3 misses and linear search 6; at 16 items, both need at most 2.

How does that apply to B-trees? #

In a B-tree, this decides the node size ^[3]. If we size nodes so that each holds about 16–32 items, we can always do linear search, which lets us do nice things like SIMD (in later sections).

What if the keys are Strings? String s are different, because their bytes are stored on the heap, not inline in the node. This changes our equation completely. We no longer get 8 keys from one cache miss; instead, each key we load is its own cache miss. So we almost always want to do binary search over String s.

A node of String s holds each key's pointer, length and capacity; its bytes are on the heap. Every comparison of a binary search follows a pointer: 3 heap reads to find one key of 8.

How does bbtree do it? Heap keys are very common, so bbtree must handle them well. bbtree introduces inline_keys, an idea databases have used for decades,^[4], similar to German strings ^[5] and StringView in Arrow ^[6].

With fixed-size inline keys, we get back the benefit of one cache miss loading 8 (or more) keys. And we only load the full key when the comparison ties.

The same node with inline keys: the first 8 bytes of every key, 64 bytes, one cache line. One compare of all of them leaves a single candidate, and only it is read from the heap.

What about keys with long prefixes? Many keys, like URLs and paths, have long prefixes. If we just take the first 8 bytes as the inline key, we may compare nothing at all. bbtree addresses this with prefix_keys: the common prefix of all keys in a node ^[7]. The beauty of prefix_keys is that no node has to store them. Every key in a node sorts between the two separators on either side of the node in its parent. So if those two separators share their first 20 bytes, every key in the node starts with the same 20 bytes.

Neighboring Wikipedia titles. The parent's two separators share their first 20 bytes, so every key of the child does too. Over the first 8 bytes, the keys all tie; past the shared 20, they all differ.

So each node only stores the length of its prefix, and keeps the window of each key right after it, which makes inline keys far more effective.

How does this apply to other key types, and how does it work with Rust's type system?

It's clear that String and Vec<u8> benefit from this optimization. But integers like u64 and u128 can too; we just need to mind the endianness: stored big-endian, their bytes sort in the same order as the numbers.

Four keys of one leaf of a tree of 10M random u64 s, as bytes: the prefix its separators share, which the leaf skips; the 2 bytes it keeps as each inline key; and the rest, read only on a tie.

For other key types, like compound keys in structs, users can implement the InlineKey trait, and when they do, we use the inline keys wherever we can.

pub trait InlineKey: Ord {
    /// How many bytes of each inline key the nodes keep: 2, 4 or 8.
    const WIDTH: InlineWidth = InlineWidth::Eight;

    /// Bytes \`offset..offset + 8\` of the key's encoding, big-endian,
    /// zero past its end, which orders as the keys do.
    fn inline_key_at(&self, offset: usize) -> InlineWord;
}

// A compound key, ordered by customer, then order: its encoding is
// both fields' bytes, one after the other.
#[derive(PartialEq, Eq, PartialOrd, Ord)]
struct OrderKey {
    customer: u32,
    order: u32,
}

impl InlineKey for OrderKey {
    fn inline_key_at(&self, offset: usize) -> InlineWord {
        let mut bytes = [0; 16];
        bytes[..4].copy_from_slice(&self.customer.to_be_bytes());
        bytes[4..8].copy_from_slice(&self.order.to_be_bytes());
        let start = offset.min(8);
        u64::from_be_bytes(bytes[start..start + 8].try_into().unwrap())
    }
}

let orders: BBTreeMap<OrderKey, u64, _> =
    BBTreeMap::with_strategy(WithInlineKey);

The trickiest part is Rust's type system. If we required every key type to implement InlineKey, bbtree couldn't be a drop-in replacement for std's BTreeMap / BTreeSet. Nightly Rust has specialization ^[8] for exactly this. For stable Rust, we specialize the common types by hand: u64, i64, u128, i128, String, str, &str, Vec<u8>, &[u8], Box<str>, Box<[u8]>, [u8; 16], [u8; 20] and [u8; 32]. So without any extra work, the built-in types are optimized, and users can still implement the trait for their own types to get the full benefit.

Results #

After these optimizations, we can show how many cache lines a lookup touches.

Cache lines brought in from memory per lookup that finds its key, 10M entries, one thread, Ryzen 9 9900X; lower is better.

Bonus: batch mode using Rust's async state machines #

So far we have focused on maximizing the value of a cache miss: packing as much information as possible into one cache line.

There's a more advanced optimization: hiding the cost of cache misses.

The simplest way to hide latency is software prefetching: while working on one key, we prefetch the next one. This usually works well, but it isn't enough for B-trees.

This is because a B-tree's memory accesses are fundamentally chained: you don't know which node to fetch next until you have searched the current one.

But B-trees are often read or built in batches, which lets us play a trick with Rust's async state machines. A batch is one call with many keys, such as BBTreeMap 's get_many_copied and insert_many: an array of keys in, an array of answers out.

The high-level idea is simple: in Rust we often treat an IO operation as a Future, and await it. In bbtree, we treat a cache miss as a Future, and await it too. Database research has interleaved lookups like this for years, by hand and with coroutines ^[9].

The code looks roughly like this (they run in a single thread):

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))
}

And search looks like this:

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)
}

Four u64 keys looked up together on one core, each key's search a task, from bbtree's own run of the batch; time is counted in turns. In its turn, a task reads the line it prefetched, steps down the tree, prefetches the next line and yields; while that line is on its way, the core runs the other tasks.

But we need to be very careful:

1. A cache miss costs 100 ns, so our Future must be as lightweight as possible. This means we can't use tokio or any general-purpose async runtime, because their overhead is already higher than a cache miss. bbtree polls its lanes with a tiny executor of its own: no allocation, no runtime.
2. Each async function in Rust is a state machine generated at compile time. We want this state machine to be as small as possible, so that switching between states is cheap.
3. There's no way to know whether a cache line is already in cache, so we have to guess. In bbtree that's not so hard: once the leaves outgrow the L2 cache, a leaf is almost always a cache miss; smaller trees look their keys up one at a time.

How do we make it correct? #

Performance optimization is easy: you simply ask Claude or Codex to make the code 10× faster on a workload. Speed is measurable, and LLMs can iterate on it relentlessly.

But making sure the code is correct is hard. Correctness is implicit: you can never list every DON'T in the prompt, you can never write enough tests to prove the code correct, and you can never enumerate every property you want to hold.

bbtree has three guards to approach correctness.

Xiangpeng is a real human behind bbtree, and the front line guarding the correctness of its code. All of the code is written by LLMs, but Xiangpeng steers every design decision, and is accountable for the code.

He spent his PhD writing many, many B-trees, including one that runs in production at Microsoft (Bf-Tree ^[10]). Choosing bbtree means offloading the attention to Xiangpeng.

Reviewers of this post #

Thanks to Andrew Lamb (InfluxData), Zac Farrell (Hotdata), Eddie Tejeda (Hotdata), Divya Ranganathan (Hotdata), Jacopo Tagliabue (bauplan), Wanxiang Zhong and Junxuan Liao for reviewing this post.