Bbtree 发布：高性能有序映射库加速 AI 基础设施

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 SELECTs 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 fragmentation22 Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau, Free-Space Management, chapter 17 of Operating Systems: Three Easy Pieces: external fragmentation is free space chopped into pieces of different sizes, so that a request can fail although the total would fit it..
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 pieces33 Not more complicated than an operating system! Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau, Operating Systems: Three Easy Pieces (2016).: 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 u64s, 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 u64s, 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 size44 Jun Rao and Kenneth A. Ross, Making B+-Trees Cache Conscious in Main Memory (SIGMOD 2000).. 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?Strings 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 Strings.

A node of Strings 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 decades5,65 Goetz Graefe and Per-Åke Larson, B-Tree Indexes and CPU Caches (ICDE 2001).6 Goetz Graefe, More Modern B-Tree Techniques (2024): keep full keys out of the comparison stream with dense, fixed-width codes, and skip the prefix a page shares., similar to German strings77 Thomas Neumann and Michael Freitag, Umbra: A Disk-Based System with In-Memory Performance (CIDR 2020); see also my post on the nature of strings. and StringView in Arrow88 Xiangpeng Hao and Andrew Lamb, Using StringView / German Style Strings to Make Queries Faster: Part 1, Reading Parquet and Part 2, String Operations (2024)..

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 node99 Rudolf Bayer and Karl Unterauer, Prefix B-Trees (TODS 1977).. 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 u64s, 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 specialization1010RFC 1210: impl specialization, unstable since 2016 (tracking issue). 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 coroutines1111 Onur Kocberber, Babak Falsafi and Boris Grot, Asynchronous Memory Access Chaining (VLDB 2015); Georgios Psaropoulos et al., Interleaving with Coroutines: A Practical Approach for Robust Index Joins (VLDB 2017); Christopher Jonathan et al., Exploiting Coroutines to Attack the "Killer Nanoseconds" (VLDB 2018)..

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.

Next, 2 of 3 Minimize instructions

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.

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.