bbtree: fastest ordered map

• Single thread
• Concurrent
• End to End
• Memory
• Architectures

These are snapshots; the interactive version switches between keys and workloads. The code is at XiangpengHao/bbtree.

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.

Case 1: faster memtable

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 fragmentation2.
3. Allocation failure can be gracefully handled.

2 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.

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.

Case 2: database index

A database’s tables change while they are read: rows are inserted, updated and deleted between queries, and every index of a table changes with it. An in-memory database keeps each in an ordered map, which has to stay sorted under these writes.

Turso, SQLite rewritten in Rust, keeps its MVCC store in memory: its tables’ rows and its indexes’ entries, each in a crossbeam-skiplist. With bbtree in their place, on Turso’s own benchmarks:

1. INSERT of random rowids: 2.22×.
2. Indexed point SELECT: 1.90×.
3. UPDATE in BEGIN CONCURRENT: 1.22×.
4. Point SELECT by rowid: 1.16×.

Turso on the End to End card: its 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.

Case 3: bbtree-mmap

bbtree-mmap allows you to build a bbtree and write it to disk once; when you need it, you can simply mmap it and use it instantly, without rebuilding anything.

cargo add bbtree-mmap

Build a bbtree and save to disk

use bbtree::unsync::BBTreeMap;
use bbtree_mmap::BBTreeMapFile;

let names = BBTreeMap::from([(7_u64, String::from("ferris")), (42, String::from("corro"))]);
BBTreeMapFile::<u64, String>::create("names.bbtree", &names)?;

Mmap bbtree and query it immediately

use bbtree_mmap::BBTreeMapFile;

let names = unsafe { BBTreeMapFile::<u64, String>::mmap("names.bbtree").open()? };
assert_eq!(names.get(&42), Some("corro"));

Time to the first answer after a restart, 10M u64 entries, Ryzen 9 9900X. std’s BTreeMap reads its file back and rebuilds; bbtree-mmap maps its file and reads only the pages the lookup touches.

How it works?

Every performance optimization should be guided by a cost model.

B-tree optimizations are simple, three easy pieces3: we just need to remember three principles, in order:

3 Not more complicated than an operating system! Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau, Operating Systems: Three Easy Pieces (2016).

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.

1. Minimize cache misses

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 size4. 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).

4 Jun Rao and Kenneth A. Ross, Making B+-Trees Cache Conscious in Main Memory (SIGMOD 2000).

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 decades56, similar to German strings7 and StringView in Arrow8.

5 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.

7 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.

8 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 node9. 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.

9 Rudolf Bayer and Karl Unterauer, Prefix B-Trees (TODS 1977).

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 specialization10 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.

10 RFC 1210: impl specialization, unstable since 2016 (tracking issue).

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 coroutines11.

11 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.

2. Minimize instructions

In general, minimizing instructions means reducing CPU time, which means two things: 1. reducing the instruction count; 2. reducing branches.

A mispredicted branch costs about 20 cycles (the time of 20 instructions), about 10% of a cache miss.

Binary search vs linear search, again

With inline keys, searching a node means searching a small array of small integers: 2 bytes a key for integers and UUIDs, 4 to 8 for strings. Now let’s compare their instructions and branches over a node of 32 keys:

1. Binary search: about 5 steps, each a compare and a branch, and the CPU typically guesses wrong half of the time. A branchless binary search12 avoids the guess, but then each step waits for the one before.
2. Linear search, without its early exit, becomes a count: compare the target with every key, and count the keys smaller than it; that number is the child to follow. It does more compares, but none branches or waits for another, a perfect fit for the CPU pipeline.

12 Paul-Virak Khuong and Pat Morin, Array Layouts for Comparison-Based Searching (2017).

Looking up 45 among seven inline keys, all in one cache line: neither search takes another miss. The count compares all of them at once: four are smaller, so it follows child 4. Binary search reaches child 4 after three compares, each waiting for the one before; over 32 keys, it takes about five.

How does bbtree search?

With SIMD, searching a node takes a handful of instructions13. One AVX-512 instruction compares the target with 32 two-byte keys at once; its result is a 32-bit mask, a bit a key, and the number of ones in the mask, its popcount, is the answer:

13 Benjamin Schlegel, Rainer Gemulla and Wolfgang Lehner, k-ary Search on Modern Processors (DaMoN 2009).

fn child_index(inline_keys: &[u16; 32], target: u16) -> usize {
    let keys = _mm512_loadu_epi16(inline_keys.as_ptr().cast());
    let smaller =
        _mm512_cmplt_epu16_mask(keys, _mm512_set1_epi16(target as i16));
    smaller.count_ones() as usize
}

The function has only three steps, all branchless and super fast:

1. _mm512_loadu_epi16 loads the inline keys into a SIMD register.
2. _mm512_cmplt_epu16_mask compares them with the target and returns a mask, a bit for each smaller key, in key order (e.g., 1111100000000000).
3. smaller.count_ones() counts the ones in the mask, which is the index of the child to follow. x86 does this in one instruction, popcnt.

We also implement the same search for ARM in NEON, so Apple Silicon and AWS Graviton work too. On x86, AVX-512 needs -C target-cpu=native (Rust 1.89 or later).

The compiler is not your friend

We often hear “write simple code and let the compiler optimize it”. The extreme version is FastLanes14, whose scalar code the compiler automatically vectorizes (generates SIMD code for).

14 Azim Afroozeh and Peter Boncz, The FastLanes Compression Layout: Decoding >100 Billion Integers per Second with Scalar Code (VLDB 2023).

15 Lookups of u64 keys that hit, in a map of 10M u64 entries, one run each on an M1 Pro, with bbtree-eval’s portable probe, before and after decision D56, which counts inline keys in NEON.

Here the compiler is not your friend. A node holds few keys, a few dozen at most, and their number is usually not a power of two. The compiler often considers it not worth vectorizing, and sometimes can’t prove it safe, so we write the SIMD by hand, and handle the boundary cases very carefully. On an M1 Pro, the compiler’s own count widened each compare’s result to 64 bits and added them up one at a time. We wrote the count in NEON by hand and changed nothing else: the same tree, the same nodes, the same cache lines. A lookup of a u64 key in a map of 10M entries went from 1,678 to 407 instructions, and from 390 to 174 ns.15

Vectorization isn’t the only problem: sometimes the compiler generates bad code because it doesn’t know the workload. For example, to compare two &[u8], Rust calls memcmp, a function call that isn’t inlined. But in bbtree, we know the keys are usually short, so instead of calling memcmp, we load the bytes as integers and compare the integers. Arrow does the same for StringView1617.

16 Xiangpeng Hao and Andrew Lamb, Using StringView / German Style Strings to Make Queries Faster: Part 1, Reading Parquet and Part 2, String Operations (2024).

17 arrow-rs #7748 compares inlined string views as one u128, and their 4-byte prefixes as one u32, instead of byte by byte.

Results

Instructions per lookup that finds its key, 10M entries, one thread, Ryzen 9 9900X; lower is better.

3. Minimize cache coherence traffic

Cache coherence traffic happens when one core writes to a cache line that other cores hold. To make sure every core sees a consistent view of memory, CPU caches implement a cache coherence protocol18. At a very high level, a write to a cache line invalidates all copies of that line in other cores.

18 Vijay Nagarajan, Daniel J. Sorin, Mark D. Hill and David A. Wood, A Primer on Memory Consistency and Cache Coherence, second edition (2020).

This causes two problems: 1. more cache misses; 2. more importantly, it puts a ceiling on the B-tree’s concurrency.

On modern hardware, a contended cache line supports at most about 10 M op/s. So if we simply put a Mutex over the B-tree, we reach at most 10 M op/s, while bbtree reaches 180 M op/s at 96 threads.

Note that a RwLock won’t help: even a read lock must increment the lock’s reader count, which is a write to its cache line.

So how does bbtree solve this?

The key idea is a version lock1920. Every node carries a version: a reader reads the version, reads the node, and reads the version again. If the version hasn’t changed, what it read is consistent; otherwise, it retries.

19 Sang K. Cha, Sangyong Hwang, Kihong Kim and Keunjoo Kwon, Cache-Conscious Concurrency Control of Main-Memory Indexes on Shared-Memory Multiprocessor Systems (VLDB 2001).

20 Viktor Leis et al., The ART of Practical Synchronization (DaMoN 2016).

Time runs down. Readers only read. Reader 1 finished before the writer changed anything, so its read stands. Reader 2 overlapped the change, finds version 8, and starts over.

This allows very high concurrency, because a read causes no write traffic at all.

But there are two things we need to be careful about.

Problem 1: we can no longer hand out a &V to the user

The value may change, or even be freed, while the user holds the reference, so it’s unsafe to use.

We can’t return a clone of V either, because V may not be Clone.

Here we use a trick similar to Bf-Tree’s21: only inner nodes are optimistic; leaves are not. This works because (1) contention usually happens at inner nodes, (2) values are stored only in leaves, and (3) leaves are only 20% of the nodes on a lookup’s path (assuming a tree of 5 levels). For Copy values, get_copied goes one step further: it reads the leaf optimistically too, copies the value out, and checks the version after, like a seqlock.

21 Xiangpeng Hao and Badrish Chandramouli, Bf-Tree: A Modern Read-Write-Optimized Concurrent Larger-Than-Memory Range Index (VLDB 2024); code at microsoft/bf-tree.

Problem 2: memory reclamation

The second problem is more subtle: if one thread is reading a node while another thread frees it, the reader may segfault.

The usual solution is epoch-based memory reclamation22, e.g., crossbeam-epoch.

22 Keir Fraser, Practical Lock-Freedom (PhD thesis, 2004); in Rust, crossbeam-epoch.

But then we either leak the epoch to the user, which is ugly and error-prone, or pin an epoch on every access (many libraries do this), which is expensive: every access is a global read and a private write.

In bbtree, we do it differently: a freed node never goes back to the allocator while the map lives. Instead, the map keeps it on a free list and reuses it for the next node it needs. The node keeps its version through both steps: freeing it bumps the version, reusing it bumps the version again, and a version only grows. So a late reader still reads a node, not arbitrary memory, finds a higher version than it saw, and retries, without any segfault.

Results

Gets of u64 keys, half of them misses, 10M entries, all threads together, a thread a core, on AWS’s c8a.metal-24xl (96 cores); the Concurrent card above has the other keys and workloads.

bbtree is wildly concurrent: its get throughput grows 83–90× as the core count grows to 96, 86–94% of linear scaling. At this thread count, bbtree is even faster than DashMap, a hashtable.

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.

Guard 1: Xiangpeng Hao

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-Tree23). Choosing bbtree means offloading the attention to Xiangpeng.

23 Xiangpeng Hao and Badrish Chandramouli, Bf-Tree: A Modern Read-Write-Optimized Concurrent Larger-Than-Memory Range Index (VLDB 2024); code at microsoft/bf-tree.

Guard 2: LLMs

No human can write better code than LLMs. All of the implementation is written by LLMs, and cross-checked by LLMs from different providers.

Guard 3: fuzzing, verification, DSTs

Conventional approaches still apply here:

1. Fuzzing runs random operations on bbtree and std’s BTreeMap side by side, checks that every answer matches, and checks the whole tree’s invariants after every operation: 8 targets, fuzzed weekly and before every release (CI).
2. Verification with Verus24 proves the critical properties of the code, e.g., that the inline keys order the same way as the keys themselves: the proofs, checked on every pull request (CI).
3. DSTs (deterministic simulation testing) with Shuttle25 and ffs26 test concurrent behavior in a deterministic and principled way: Shuttle runs each test under thousands of thread schedules on every pull request (CI); ffs, run by its author, found a race Shuttle had missed (issue #9), now fixed and tested.

24 Andrea Lattuada et al., Verus: Verifying Rust Programs using Linear Ghost Types (OOPSLA 2023); code at verus-lang/verus.

25 Shuttle, a library for testing concurrent Rust code, from AWS.

26 ffs, fork-based deterministic concurrency testing.

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.