B-Trees vs LSM-Trees: Choosing a Storage Engine

B-trees and LSM-trees are the two data structures nearly every database’s storage engine is built on, and the choice between them is really a choice about which side of the read/write tradeoff a workload sits on: B-trees update records in place for consistently fast reads, while LSM-trees batch writes sequentially to disk and pay for it with more work at read time.

How a B-tree stores data

A B-tree keeps data sorted in a balanced tree of fixed-size pages, each holding many keys and pointers to child pages. Reading a value means walking down from the root, comparing keys at each level, until you reach the leaf page holding the record — a small, bounded number of page reads regardless of table size, which is why B-trees give predictable, low-latency lookups.

Writing to a B-tree means finding the correct page and updating it in place. If the page is full, it splits into two, and that split can cascade up the tree. This in-place update pattern means a single small write can touch a page in memory that then needs to be flushed to disk in its entirety — the well-known write amplification problem that comes with maintaining a balanced, sorted structure on disk. This is also why B-tree indexes need periodic maintenance, and why database vacuuming and index maintenance exist as an operational concern for traditional relational databases.

How an LSM-tree stores data

A log-structured merge-tree takes a different approach: writes never touch the on-disk structure directly. Instead, they land in an in-memory buffer (a memtable), which is simply appended to sequentially. Once that buffer fills up, it’s flushed to disk as an immutable, sorted file. Over time, a background process merges these files together — compaction — discarding overwritten or deleted values and keeping the number of files a read has to check from growing unbounded.

Because writes are just sequential appends to memory and, eventually, disk, LSM-trees can sustain much higher write throughput than B-trees, especially on storage where sequential writes are cheaper than random ones. The cost shows up on the read side: a single lookup may need to check the memtable and multiple on-disk files before it can be sure it has the most recent value for a key, which is why LSM-tree—backed engines lean heavily on Bloom filters to skip files that provably don’t contain a given key, and why compaction itself consumes background I/O and CPU that a pure B-tree engine doesn’t need.

B-tree vs LSM-tree

	B-tree	LSM-tree
Write pattern	In-place update, random I/O	Sequential append, then background compaction
Write throughput	Lower — write amplification from page updates	Higher — writes are cheap appends
Read latency	Consistently low — bounded page walk	Variable — may check multiple files
Read amplification	Low	Higher, mitigated by Bloom filters and caching
Background maintenance	Page splits, vacuuming	Compaction
Common in	PostgreSQL, MySQL InnoDB, most traditional RDBMSes	Cassandra, RocksDB, LevelDB, many time-series and key-value stores

Why databases pick one or the other

Traditional relational databases — PostgreSQL and MySQL among them — default to B-tree storage because their workloads have historically skewed toward mixed read/write access with a strong expectation of consistent read latency, and because B-trees pair naturally with the range scans and covering indexes that relational query patterns rely on. This is distinct from the choice covered in hash index vs B-tree index, which compares two structures within the B-tree-oriented world rather than across the write-optimized/read-optimized divide.

Write-heavy systems — time-series ingestion, event logging, wide-column stores handling constant high-volume writes — more often reach for an LSM-tree engine, because the workload’s bottleneck is ingesting data as fast as possible, and read latency variance matters less than sustained write capacity. Some modern engines blur the line entirely, using LSM-style writes with additional structures layered on top to bound read amplification, which is part of why understanding how database indexes work in general matters more than memorizing which engine uses which structure — the underlying tradeoff is the constant, even as implementations evolve.

Making the choice in practice

Most application developers don’t choose a storage engine’s internal data structure directly — they choose a database, and the data structure comes with it. But understanding which one you’re running on explains real operational behavior: why a write-heavy PostgreSQL table benefits from tuning autovacuum aggressively, why an LSM-backed store like Cassandra can absorb huge write bursts but occasionally shows read latency spikes during compaction, and why EXPLAIN ANALYZE on a B-tree-backed table gives such consistent, predictable plans compared to profiling a compaction-heavy LSM store.

The takeaway

B-trees update data in place, which keeps reads fast and predictable at the cost of write amplification; LSM-trees defer that cost by writing sequentially and merging in the background, which favors write throughput at the cost of read amplification and periodic compaction overhead. Neither is strictly better — the right one depends on whether a workload is bottlenecked on ingesting writes or on serving consistently fast reads, and most systems that need both eventually reach for a hybrid design rather than a pure version of either.