Pick any database and look closely enough at its storage layer, and you will find it has quietly taken a side. Postgres, MySQL's InnoDB, and most traditional relational engines are built on B-trees. Cassandra, RocksDB, LevelDB, ScyllaDB, and TiKV are built on log-structured merge-trees, or LSM-trees. This is not a cosmetic detail. The choice of on-disk data structure determines whether an engine is naturally fast at reads or fast at writes, how it behaves under load, and how much disk it consumes to store the same data. Understanding the tradeoff is one of the most transferable pieces of knowledge in backend engineering, because it applies the same way whether you are choosing a database or debugging one.
Two philosophies of writing to disk
A B-tree updates data in place. When you write a row, the engine walks the tree to the correct leaf page and modifies it where it lives on disk. If the page is full, it splits. This keeps the tree balanced and makes reads wonderfully predictable, but the write path pays for it: in-place updates scatter small, random writes across the disk, and over time pages split and fragment.
An LSM-tree refuses to do in-place updates at all. Incoming writes go first into an in-memory structure (the MemTable) and an append-only log. When the MemTable fills, it is flushed to disk as an immutable, sorted file — an SSTable — in one sequential pass. Nothing already on disk is mutated; new data simply accumulates in new files. This turns a storm of random writes into a stream of large sequential ones, which is exactly the access pattern that both spinning disks and SSDs handle best. The cost is deferred, not avoided: those files must later be merged and rewritten by a background process called compaction.
The three amplifications you cannot all win
The cleanest way to reason about storage engines is through three ratios. As TiKV's engineering documentation defines them: write amplification is the amount of data written to the device versus the amount written to the database; read amplification is the number of disk reads per query; and space amplification is the amount of data on the device versus the amount logically in the database.
The central, humbling result is that a data structure can optimize for at most two of these three. You do not get a free lunch. A B-tree has lower read amplification than an LSM-tree; an LSM-tree has lower write amplification than a B-tree for many write-heavy workloads. Something always gives.
The nuance worth internalizing is that "write amplification" cuts two ways. An LSM-tree's compaction can rewrite the same data many times over its lifetime — a leveled LSM can rewrite on the order of tens of times as data migrates down levels. That sounds bad, but every one of those rewrites is sequential and disk-friendly, whereas a B-tree's smaller write volume is made of expensive random I/O. Which engine "wins" on write amplification therefore depends on record size, page size, and workload — recent research at USENIX FAST '22 was devoted precisely to closing this gap, which tells you it is genuinely contested rather than settled.
How LSM-trees claw back read performance
If an LSM-tree never mutates old files, how does it answer a point query? In the worst case it has to look in several places: the MemTable first, then potentially each level of SSTables from newest to oldest, because a key's current value might live in any of them. That is the read amplification you pay for cheap writes.
LSM engines fight back with two devices. Bloom filters are compact probabilistic structures that can tell you a key is definitely not in a given SSTable, letting the engine skip reading that file entirely. Fence pointers (sparse indexes over each sorted file) narrow a lookup to the specific block that could contain the key. Together they mean a well-tuned LSM often touches far fewer files than the naive worst case suggests. Conceptually, the read path looks like this:
# Illustrative LSM point-read path (not real engine code)
def get(key):
if key in memtable: # 1. in-memory, newest data
return memtable[key]
for sstable in levels_newest_to_oldest():
if not sstable.bloom.might_contain(key):
continue # 2. Bloom filter skips most files
block = sstable.fence_pointer_lookup(key)
if key in block:
return block[key] # 3. read only the candidate block
return NOT_FOUNDChoosing a side in practice
The decision is workload-driven. If your system is write-heavy — time-series ingestion, event logging, metrics, high-volume key-value traffic — an LSM engine's sequential writes and high throughput are a natural fit, which is why Cassandra, ScyllaDB, and RocksDB-backed systems dominate there. If your workload is read-heavy or transactional, with lots of point lookups and range scans over data that is updated in place, a B-tree engine like Postgres or InnoDB gives you low, predictable read latency.
Two operational realities deserve a mention. LSM compaction runs in the background and periodically competes for disk and CPU, which can show up as latency spikes — something to plan for, not to be surprised by in production. And on the space axis, LSM-trees can hold onto superseded versions of a key until compaction reclaims them, while B-trees can leave partially empty pages after splits and deletes; neither is automatically more compact. As always, the right answer is to match the engine to your dominant access pattern rather than to a benchmark headline.
Key Takeaways
- Every storage engine trades reads against writes. B-trees update in place (great reads, random writes); LSM-trees append and compact (great writes, more read work).
- You can optimize at most two of read, write, and space amplification — there is no structure that wins all three.
- LSM write amplification is high but sequential; B-tree write amplification is lower but random. Which wins is workload-dependent, not absolute.
- Bloom filters and fence pointers are what make LSM reads practical by skipping files that cannot contain the key.
- Choose by dominant access pattern: write-heavy and ingest-oriented leans LSM; read-heavy and transactional leans B-tree. And plan for compaction's background cost.