bbtree: fastest ordered map
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 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.
Next, 2 of 3 Case 2: database index
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 `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 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?**`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 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 `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`1010RFC 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.
Notes
1. Jim Gray and Andreas Reuter, _Transaction Processing: Concepts and Techniques_ (1993), as quoted by Goetz Graefe in Modern B-Tree Techniques (2011).
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. 3. Not more complicated than an operating system! Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau, Operating Systems: Three Easy Pieces (2016). 4. Jun Rao and Kenneth A. Ross, Making B+-Trees Cache Conscious in Main Memory (SIGMOD 2000). 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). 9. Rudolf Bayer and Karl Unterauer, Prefix B-Trees (TODS 1977). 10. RFC 1210: impl specialization, unstable since 2016 (tracking issue).
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). 12. Paul-Virak Khuong and Pat Morin, Array Layouts for Comparison-Based Searching (2017). 13. Benjamin Schlegel, Rainer Gemulla and Wolfgang Lehner, k-ary Search on Modern Processors (DaMoN 2009). 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. 16. arrow-rs #7748 compares inlined string views as one `u128`, and their 4-byte prefixes as one `u32`, instead of byte by byte. 17. Vijay Nagarajan, Daniel J. Sorin, Mark D. Hill and David A. Wood, A Primer on Memory Consistency and Cache Coherence, second edition (2020). 18. 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). 19. Viktor Leis et al., The ART of Practical Synchronization (DaMoN 2016).
20. 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. 21. Keir Fraser, Practical Lock-Freedom (PhD thesis, 2004); in Rust, crossbeam-epoch. 22. Andrea Lattuada et al., Verus: Verifying Rust Programs using Linear Ghost Types (OOPSLA 2023); code at verus-lang/verus. 23. Shuttle, a library for testing concurrent Rust code, from AWS. 24. ffs, fork-based deterministic concurrency testing.