B-Tree vs LSM-Tree: What My Own Benchmarks Actually Showed

Postgres, MySQL, and SQLite all default to B-trees. Cassandra, RocksDB, and LevelDB are all LSM-trees. Both are solving the exact same problem, storing sorted data durably on disk so it can be read back efficiently, and mature engineering teams have picked opposite answers. That's usually a sign the "right" answer depends entirely on what you're optimizing for, not that one approach is simply better.

I spent the last few months building VellumDB, an LSM-tree key-value store in Rust, specifically to stop taking that tradeoff on faith and actually measure a piece of it. Before the numbers, one thing worth being upfront about: I didn't build a B-tree in this project. What I have is real, measured data comparing VellumDB against a deliberately naive baseline, and a conceptual explanation of where a real B-tree would actually sit relative to both. I'll be clear throughout about which is which.

Two different bets on the same problem

A B-tree keeps data sorted on disk at all times. Every write finds the right place in the tree and updates it there, in place. This makes reads fast and predictable, the tree is always in its final, queryable shape, but it means every write potentially touches several disk pages scattered around the file, in effectively random locations.

An LSM-tree, the design behind VellumDB, bets the other way. Writes go to an in-memory buffer (the memtable) and a sequential log first, both cheap, and only periodically get flushed to disk as sorted, immutable files. Nothing on disk is ever edited in place, files just accumulate and later get merged back together (compaction). This makes writes cheap and sequential, but it means a single read might have to check several files instead of one, and the same data can get rewritten more than once as compaction consolidates it.

Neither of these is free. The interesting part is exactly what each one costs, and that's the part I could actually go measure.

What I actually built and compared

To get a real, honest signal rather than an assumption, I benchmarked VellumDB against the most naive possible persistent store: a plain HashMap that rewrites its entire dataset to a single file on disk on every single write. No log, no sorted structure, no in-place updates, just "keep everything in memory, and periodically dump all of it to disk from scratch."

This is not a B-tree. A real B-tree only touches the handful of pages a given write actually affects, not the whole dataset, so its write cost scales with tree depth (logarithmically), not with total data size (linearly), which is what the naive baseline does. The naive baseline is a useful stand-in for one specific idea, cost that grows with how much data you already have stored, not a stand-in for B-trees specifically. With that caveat in place, here's what came out of it.

Writes: VellumDB wins, and the gap only grows

At a modest 200 keys, already:

sequential writes:  VellumDB 3.4x faster
random writes:      VellumDB 5.5x faster

This isn't surprising once you know why: the naive baseline's cost per write is proportional to everything it's ever stored, so its cost curve gets steeper as the dataset grows, while VellumDB's write path (append to a log, insert into an in-memory sorted map) stays close to flat. Run this at a larger n and the gap would widen further, that's the whole point of the naive baseline existing: to make the shape of that cost visible.

A real B-tree wouldn't show this gap nearly as dramatically, because its per-write cost is bounded by tree depth rather than total size. It would still typically lose to an LSM-tree on raw write throughput, because "append to a log" is cheaper than "find the right page and update it," even when that page-find is fast, but the gap would be a small constant factor, not something that grows with dataset size the way it does against the naive baseline here.

Reads: the naive baseline wins, dramatically, and it's not a fluke

existing-key reads:  naive up to 485x faster
missing-key reads:   naive is faster here too, no disk touch at all

This looks bad for VellumDB until you notice why it's true: the naive baseline holds everything in RAM, with zero persistence overhead on the read path at all, that's only viable because it's already paying for that with an unbounded, ever-growing per-write cost. VellumDB's reads have to check a sorted in-memory buffer, then potentially several sorted files on disk, each behind a Bloom filter check to skip files that definitely don't have the key. That's real overhead compared to "look it up in a hashmap already sitting in memory."

This is closer to where a real B-tree's actual advantage lives. A B-tree's data is always fully sorted and organized on disk, so a read is a single, predictable descent through a small number of pages, no equivalent of "check several files." That's the genuine, well-known reason B-trees remain the default for read-heavy, general-purpose databases: their read path doesn't carry LSM's file-fragmentation cost. My naive baseline overstates this comparison (nothing is actually faster than "already in RAM"), but the direction is the same one a real B-tree vs LSM-tree comparison would show, reads that don't have to reconcile scattered pieces are simpler and faster.

The cost LSM pays that a B-tree doesn't: write amplification

This is the number I found most interesting, because it isn't a comparison against anything, it's a cost internal to the LSM design itself. I ran a workload with a few rounds of overwrites and flushes, then measured the actual bytes sitting on disk against the logical size of the live data:

logical live data:            56,000 bytes
on-disk before compaction:    211,516 bytes   (3.8x)
on-disk after compaction:      69,140 bytes   (compaction reclaimed 67%)

That 3.8x isn't a bug, it's overwritten and stale data sitting in old, not-yet-compacted files, because SSTables are immutable and an overwrite doesn't erase the old copy, it just gets shadowed by a newer one until compaction physically removes it. A B-tree doesn't have this problem at all: an in-place update overwrites the old value directly, there's no equivalent of "stale copies accumulating until a background job cleans them up." This is write amplification, and it's the real, structural price of the design that made VellumDB's writes fast in the first place: deferring the cost of reconciling old and new data instead of paying it immediately, on every write, the way a B-tree does.

Bloom filters: the mitigation, not the cure

LSM's read cost (checking multiple files) gets partly clawed back with Bloom filters, a cheap, in-memory check that can rule out a file without opening it:

missing-key read, 100 sstables:  165µs with a bloom filter, 14.5ms without, roughly 40-50x

That's a real, substantial improvement, but it's a mitigation of a cost the design introduced, not proof the cost doesn't exist. A B-tree never needed this optimization in the first place, because it never scattered a key's history across multiple files to begin with.

So which one is actually better?

Neither, and that's not a cop-out, it's the actual, honest answer these numbers point to. If your workload writes a lot and reads comparatively rarely, or you can tolerate reads that cost a bit more in exchange for writes that scale, an LSM-tree is the better bet, that's exactly why Cassandra and RocksDB exist. If your workload is read-heavy and you want every read to be a single, predictable, in-place lookup without worrying about background compaction eating disk I/O at unpredictable times, a B-tree is the better bet, that's exactly why Postgres and SQLite still default to one.

What I can say with actual confidence, backed by numbers I measured rather than numbers I assumed: the LSM design's write advantage is real and grows with data size, its read cost is real but mitigated by Bloom filters, and its write amplification (rewriting the same logical data multiple times via compaction) is a real, distinct cost that a B-tree's in-place updates simply don't have. Building a real B-tree to put next to these numbers directly is a natural next project, and if I do it, this is the article I'd come back and revise.

The full benchmark suite, including the naive baseline comparison above, is on GitHub if you want to run it yourself.