bbtree beats skiplists by up to 6.8× in LSM-tree memtables
Bbtree: Fastest Ordered Map
bbtree is a B-tree ordered map built around a simple cost model: minimize chained cache misses. Nodes hold 16–32 items so linear search and SIMD beat binary search, inline keys pack eight keys into one cache line, and prefix keys skip shared bytes in URLs and paths. Dropped into four LSM-trees, it beat skiplists by 1.37–6.83×, sped up Turso's inserts 2.22×, and mmaps from disk with no rebuild after restart.
In bbtree, we treat a cache miss as a Future, and await it too.
- geraneum
> Production-ready by formal verification, model checking, deterministic simulation, fuzzing, and lots of testing.
What does model checking mean here?
- tyilo
> No human can write better code than LLMs.
Bold claim...
- jared_hulbert
Very nice work. I'm working on stuff... adjacent to this I guess. I've been harping on the ideas that we have to be much more willing to reach for intrinsics, be laser focused on the cache lines, treat DRAM more like an async block device, but I can't believe I haven't thought to show the impact of coherence traffic! When I get some time I might try to apply some of my tricks to bbtree. DM me. I'd love to be able to reach out when I do.