Every database has to answer a deceptively hard question: how do you organize data on disk so reads and writes are both fast? For decades, the default answer was the B-tree. It’s the structure behind traditional relational databases like MySQL’s InnoDB and PostgreSQL’s default indexes. But over the past fifteen years, a different structure has quietly taken over the write-heavy corners of the database world: the log-structured merge tree, or LSM tree.

If you’ve used Cassandra, RocksDB, LevelDB, HBase, or even newer time-series and key-value stores, you’ve been relying on an LSM tree without necessarily knowing it. Understanding why it exists explains a lot about how modern infrastructure handles scale.

The B-Tree Baseline

A B-tree keeps data sorted on disk in a balanced tree structure, which makes point lookups and range scans efficient. The catch is that every write, in the worst case, means finding the right leaf node and modifying it in place. On spinning disks, and even on SSDs, in-place random writes are expensive compared to sequential ones. As write volume climbs, a B-tree’s performance degrades because the disk spends more time seeking than transferring data.

That tradeoff was tolerable when databases were mostly read-heavy and wrote modest volumes of transactional data. It becomes a real bottleneck for workloads like event logging, metrics ingestion, or high-throughput OLTP, where writes dominate.

Enter the LSM Tree

An LSM tree takes a different philosophy: never do a random write if you can avoid it. Incoming writes first land in an in-memory structure, often called a memtable, and get appended to a write-ahead log for durability. Once the memtable fills up, it gets flushed to disk as an immutable, sorted file, commonly called an SSTable (sorted string table).

Over time you accumulate many of these immutable files. Reads have to check the memtable and potentially multiple SSTables, merging results on the way out. Writes stay fast because they’re always sequential appends, never in-place edits.

Compaction: The Hidden Cost

The tradeoff shows up later, in a background process called compaction. Because SSTables are immutable, updates and deletes don’t modify existing files, they just write new entries that supersede old ones. Compaction periodically merges multiple SSTables together, discarding stale or deleted data and keeping the number of files reads have to check under control.

Compaction is the part of LSM tree design that engineers actually spend most of their tuning time on. Run it too aggressively and you burn disk I/O and CPU that could go toward serving requests. Run it too lazily and read performance degrades as reads fan out across more and more files, a problem often called read amplification. Different databases implement different compaction strategies, like leveled or size-tiered compaction, each making different tradeoffs between write throughput, read latency, and space usage.

Where LSM Trees Show Up

The appeal of LSM trees tracks closely with the rise of distributed, write-heavy systems. Cassandra and HBase built their storage layer around them from the start, because they were designed for ingesting large volumes of data across many nodes. RocksDB, built on Google’s LevelDB, took the idea further and became an embeddable storage engine that other systems build on top of, showing up inside CockroachDB, TiDB, and various stream processing tools.

Choosing Between Them

Neither structure is universally better. B-trees still win for read-heavy workloads with lots of range queries and moderate write volume, which is why they remain the default in most relational databases. LSM trees win when write throughput matters more than read latency, and when you can tolerate the operational overhead of compaction.

The broader lesson is that storage engine design is never free of tradeoffs. Every choice to optimize writes costs something on the read side, and vice versa. When evaluating a database for a write-heavy workload, it’s worth asking not just how fast it ingests data, but how it handles compaction, and what that means for tail latency once the disk fills up with years of accumulated SSTables.