bbtree: A Rust Ordered Map Claiming Up to 6.83x Over Skiplists, and What Commenters Doubt
bbtree is a Rust ordered map (B-tree) that its author claims outperforms skiplists and std::collections::BTreeMap on cache-bound workloads, reporting speedups of 1.37-6.83x when used as the memtable in four production LSM-trees, 2.22x faster inserts as an in-memory database index, and a 160-2,500x faster first answer when memory-mapped from disk. The post appeared on Hacker News as "Bbtree: Fastest Ordered Map" (153 points, 21 comments), hosted at bbtree.xiangpeng.systems and submitted by the user aoli-al.
What bbtree claims to do
The core argument is that B-trees underpin most big-data systems, so a faster B-tree improves everything layered on top of it: agent memory, LLM training, RAG, KV stores, state caching, and vector search. The post presents three representative use cases with benchmark numbers.
1. Replacing the skiplist in LSM-tree memtables
Every LSM-tree keeps recent writes in memory in an ordered map called the memtable. In Rust, that map is usually a skiplist such as crossbeam-skiplist. The post reports that bbtree replaces it at 1.37-6.83x the speed, measured on each system's own benchmark, single-threaded, on a Ryzen 9 9900X, changing only the map:
- fjall: gets 2.47x, inserts 1.61x, write batches 3.00x
- SlateDB: gets 1.71x, puts 1.65x, write batches of 10 rows 2.36x
- Tonbo: 10M-row writes 6.83x, conflict-checked transactions 4.10x
- Lance's MemWAL index (its own skiplist): point lookups 2.19x, batched lookups 3.94x, batched puts 4.21x
The stated interface advantage is that bbtree exposes an API similar to crossbeam-skiplist but simpler, with no epoch and no need to reason about when to pin or re-enter an epoch. Memory management is also more controllable: a custom allocator is supported from day one, allocation never happens at irregular (non-power-of-two) sizes, which avoids external fragmentation, and allocation failure can be handled gracefully.
2. In-memory database index
Replacing Turso's skiplists, the post reports inserts 2.22x faster and indexed SELECTs 1.90x faster.
3. Memory-mapping a bbtree from disk
Because a bbtree can be mmapped directly, there is no rebuild step after a restart. The post reports the first answer arriving 160-2,500x sooner than with std's BTreeMap.
The cost model behind the design
The post frames all optimizations around three costs, listed in priority order:
- The number of chained cache lines touched. A cache miss costs about 100 ns.
- The number of instructions executed. An instruction costs about 0.5 ns.
- Cache coherence traffic, which matters most for concurrent access. It forces a cache miss and costs slightly more than 100 ns.
Because a cache miss is roughly 200x the cost of an instruction, the dominant goal is to minimize cache misses and, for each miss, to narrow the search space as much as possible.
Linear search beats binary search below about 16 items
The post runs a thought experiment on a sorted array of u64 values. Binary search halves the remaining search space per cache miss. Linear search rules out cache_line_size / item_size items per miss, which is 64 / 8 = 8 for u64. The break-even point is therefore about 16 items, where both strategies cost at most two cache misses. Two caveats push the real break-even point higher: the CPU prefetcher may fetch subsequent cache lines on its own, favoring linear search, and linear search is simpler, allowing more CPU pipeline parallelism. The post illustrates this with 64 sorted u64 values, 8 per cache line: binary search needs 3 misses and linear search 6 at that size, but at 16 items both need at most 2.
This is why bbtree sizes nodes to hold roughly 16-32 items, so linear search can always be used, which also makes SIMD viable. The design follows earlier work on cache-conscious B+-trees (Rao and Ross, SIGMOD 2000).
inline_keys: making heap-allocated keys cache-friendly
String keys break the arithmetic above. A String's bytes live on the heap, not inline in the node, so loading one key becomes its own cache miss rather than one miss yielding 8 keys. For String keys, a binary search is therefore usually preferable.
bbtree's answer is inline_keys, which the post describes as an idea databases have used for decades, similar to German strings and to StringView in Apache Arrow. A fixed-width code derived from each key is stored inline in the node. With fixed-size inline keys, one cache miss again loads 8 or more keys, and the full key is loaded only when a comparison ties.
prefix_keys handles long shared prefixes
Keys such as URLs and file paths often share long prefixes, so taking only the first 8 bytes as the inline key may compare nothing useful. bbtree stores a prefix_keys value: the common prefix of all keys in a node. No node has to store those bytes explicitly. Every key in a node sorts between the two separators on either side of it in the parent, so if those two separators share their first 20 bytes, every key in the child node starts with the same 20 bytes. Each node therefore stores only the length of its prefix and keeps the window of each key immediately after it. The technique dates to Prefix B-Trees (Bayer and Unterauer, TODS 1977).
Integer keys also benefit
Integer keys such as u64 and u128 can use the same trick, provided they are stored big-endian so their bytes sort in the same order as the numbers.
The InlineKey trait and Rust's type system
Users can implement the InlineKey trait for their own key types, including compound struct keys. The trait declares a byte width of 2, 4, or 8 and a function that returns the 8 bytes of the key's encoding at a given offset, big-endian and zero-padded past the end:
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;
}
The post identifies Rust's type system as the trickiest part. Requiring every key type to implement InlineKey would stop bbtree from being a drop-in replacement for std's BTreeMap and BTreeSet. Nightly Rust has specialization (RFC 1210, unstable since 2016) for exactly this purpose. For stable Rust, bbtree hand-specializes the common types: u64, i64, u128, i128, String, str, &str, Vec
Batch mode: treating a cache miss as a Future
The second class of optimization is hiding latency rather than reducing it. Software prefetching helps but is not enough for B-trees, because a B-tree's memory accesses are fundamentally chained: the next node cannot be fetched until the current one has been searched.
bbtree exploits the fact that B-trees are often read or built in batches. Batch APIs such as get_many_copied and insert_many take an array of keys in and return an array of answers out. Internally, bbtree treats a cache miss as a Future and awaits it, in the same way Rust code awaits an IO operation. The shape of the code is roughly:
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)
}
Three constraints shape the implementation. First, a cache miss costs about 100 ns, so the Future must be extremely lightweight; a general-purpose runtime such as tokio would cost more in overhead than the cache miss itself, so bbtree polls its lanes with a tiny executor of its own that does no allocation and uses no runtime. Second, the per-function async state machine generated at compile time must be as small as possible so state switches are cheap. Third, since there is no way to know whether a cache line is already resident, bbtree guesses: once leaves outgrow the L2 cache, a leaf is almost always a miss, while smaller trees look keys up one at a time. The post notes that database research has interleaved lookups this way for years, by hand and with coroutines.
Correctness
The post is explicit that speed is easy and correctness is hard: performance is measurable and LLMs can iterate on a workload, but correctness is implicit, and no prompt lists every DON'T, no test suite proves the code correct, and no one can enumerate every desired property. The post states that bbtree has three guards to approach correctness. A commenter quotes the project's own framing of that work as: "Production-ready by formal verification, model checking, deterministic simulation, fuzzing, and lots of testing." The references cited around this section point to Verus for verifying Rust programs with linear ghost types, AWS's Shuttle for testing concurrent Rust code, and ffs, a fork-based deterministic concurrency testing tool.
Where the claims meet pushback
The Hacker News discussion is notably skeptical of the word "fastest," and several commenters supply counter-data.
A real workload where the swap is slower
Commenter virtualritz tested bbtree in a 3D boolean mesh kernel, swapping out std::BTreeMap with no other code changes, and reported regressions: union and difference operations on meshes of 96 to 1536 faces became 11% to 21% slower, and an intersection stage became 16% to 34% slower. On a larger fixture, a Nefertiti bust scan with one million vertex IDs (best of 3, seconds):
| cage op | std | bbtree |
|---|---|---|
| difference | 84.2 | 83.0 |
| union | 83.2 | 85.6 |
| intersection | 61.3 | 67.1 |
| limit-surface difference (best of 2) | 123.9 | 147.2 |
The conclusion drawn was that bbtree's advantages likely hold only under a specific and possibly narrow set of use cases, and that a general-purpose map such as std::BTreeMap has to make compromises to hold up across arbitrary workloads.
Tries are the real competitors
Commenter nicknash argued that the natural competitors to a B-tree are trie-based structures, including burst tries, optimized q-fast and p-fast tries, level-compressed tries, bucketed tries, and path-compressed tries, plus optimized stratified trees such as van Emde Boas layouts where key length permits. The argument is that fully comparison-based structures are rarely necessary, since integers, floats, and strings can be handled by lexicographic structures, and that tries perform particularly well on uniform random data with log-logarithmic operation times. The commenter remained skeptical of the "fastest" label while calling the work good.
Memory usage on string keys
Commenter ytxm measured a map from String to usize over /usr/share/dict/words, with the value being the dictionary offset, and reported bbtree using about 40% more RAM than std::collections::BTreeMap. They noted this is a data point rather than a refutation, because the post's lower-memory claim was specifically about integer keys. The same commenter was critical of the animated web-paper format, saying the dynamic elements required skipping past as much as reading.
Skepticism about framing
Other comments questioned the project's positioning. One commenter quoted "No human can write better code than LLMs" and called it a bold claim; another asked what model checking means in this context; another dismissed the write-up as "AI slop" and objected to the opening quote; one simply asked for the source.
Practitioner interest
Not all reaction was negative. Commenter elendilm described using BTreeMap to deduplicate work in the scatter phase of "smart batching" in their system, Dip, and said this deduplication is the slowest phase on most bulk write workloads of 200k+ inserts in a single request, sometimes taking up to 3x the combined time of fanout, database writes, commits, and gathering. They planned to try bbtree there. Commenter jared_hulbert, working on adjacent problems, highlighted the post's treatment of coherence traffic and said they intended to apply their own techniques to bbtree.
Key takeaways
- bbtree is a Rust ordered map presented as a drop-in replacement for std::BTreeMap and BTreeSet that also replaces skiplists in LSM-tree memtables.
- Its headline numbers come from four LSM-tree integrations on each system's own benchmark (up to 6.83x), an in-memory database index (2.22x inserts, 1.90x indexed SELECTs), and mmapped disk-resident trees (160-2,500x faster first answer than std's BTreeMap).
- The design is organized around cache misses via three mechanisms: 16-32 item nodes searched linearly, inline_keys that keep fixed-width key codes in the node, and prefix_keys that store only the shared prefix length of a node's keys.
- Batch APIs hide cache-miss latency by treating a miss as an awaitable Future and polling lanes with a purpose-built, allocation-free executor rather than tokio.
- Independent testing reported regressions on a 3D boolean mesh kernel and about 40% higher memory use on a String-keyed map, so the performance claims appear workload-dependent rather than universal.
- The post was reviewed before publication by Andrew Lamb (InfluxData), Zac Farrell, Eddie Tejeda, and Divya Ranganathan (Hotdata), Jacopo Tagliabue (bauplan), Wanxiang Zhong, and Junxuan Liao.