Advanced System Design Fundamentals
Vote

0% completed

​

Storage Engines: B-Trees vs LSM-Trees

  1. Two Ways to Change a Row on Disk
  1. The B-Tree: In-Place Updates, Organized for Reads
  1. The LSM Tree: Sequential Writes, Organized for Writes
  1. The Three Amplifications, With a Worked Number
  1. How Each Engine Fails
  1. The Senior Decision

1. Two Ways to Change a Row on Disk

Every database has a layer that decides how rows are physically arranged on disk and what happens to those bytes when a row changes. That layer is the storage engine. You already know what an index is and what it does for a query. This lesson is about the machinery underneath the index, because when a database fails under peak traffic, the storage engine is usually the cause, not the query planner.

Two designs account for nearly everything you will operate.

  • A B-tree engine updates rows in place and is organized around fast reads.
  • A log-structured merge tree (LSM tree) never updates anything in place and is organized around fast writes.

To choose between them, or to diagnose the one you already run, you need to know what each design does with a write after your application has finished with it.

Three quantities measure that difference, and they come back in every section of this lesson.

  • Write amplification is the ratio of bytes written to the device over bytes written by the application.
  • Read amplification is the number of separate places the engine must consult to answer a single-row read.
  • Space amplification is the ratio of bytes stored on disk over bytes of live data.

No engine keeps all three low. Every engine, and every configuration knob inside it, trades one against the others.

2. The B-Tree: In-Place Updates, Organized for Reads

PostgreSQL, MySQL with InnoDB, SQL Server, and most relational databases store rows in B-trees. Start with the physical picture. Data is stored in fixed-size pages, 8 KB in Postgres and 16 KB in InnoDB. A write locates the page that owns the key and overwrites the value where it already sits.

Page splits are where write amplification begins. Pages fill up. When an insert arrives at a full page, the engine splits it: roughly half the entries move into a newly allocated page, and the parent gains a separator key and a pointer to it. A split can cascade when the parent is also full, and a split that reaches the root is how the tree grows taller.

Every split turns one logical write into several physical writes, and it leaves both pages with free space, so the same data gradually takes up more pages and costs more reads to scan.

One insert into a full page becomes four physical writes, and leaves both pages with free space that later reads still have to scan.
One insert into a full page becomes four physical writes, and leaves both pages with free space that later reads still have to scan.

What Postgres adds. In Postgres the table (the heap) and its indexes are separate structures. Updating an indexed column writes a new heap row and new entries in every index on that table, so the multiplier compounds with each index you add. Postgres reduces this with heap-only tuple updates (HOT updates): when the changed column is not indexed and the page has free space, the new version stays on the same page and no index entry is written.

Separately, dead row versions accumulate until vacuum reclaims them. A table with heavy updates and under-tuned autovacuum accumulates bloat, doing steadily more I/O for the same amount of live data. This is one of the most common unexplained slowdowns in production Postgres, and it starts in the storage engine rather than in any single query.

What InnoDB adds. InnoDB stores the table itself in primary key order, an arrangement called a clustered index. Primary key lookups are therefore one traversal, but every secondary index leaf stores the primary key rather than a direct row pointer, so a secondary index lookup costs a second traversal. InnoDB can also collect modifications to non-unique secondary indexes in the change buffer and apply them later in batches, which is a B-tree engine making up for its own weakness at random writes. That buffer is switched off by default in current versions.

The random I/O problem. Updating in place scatters writes across the device. On rotating disks this was severe. On SSDs it is expensive rather than fatal, but the imbalance is permanent. A read walks one ordered structure in a few steps, while a write pays for the write-ahead log record, the page write, a share of page splits, and index maintenance.

Write amplification, in numbers. For a mixed relational workload, 2x to 4x is typical: your application writes 10 MB/s and the disk sees 20 to 40 MB/s. Update-heavy tables carrying many indexes run higher.

3. The LSM Tree: Sequential Writes, Organized for Writes

Cassandra, ScyllaDB, RocksDB, and the many stores built on RocksDB use log-structured merge trees. The organizing rule is that nothing already written to disk is ever modified. The write path has three stages.

  1. Write-ahead log and memtable. Each write appends one record to a log for crash recovery and inserts the row into a sorted in-memory structure called the memtable. Both operations are sequential and run at memory speed, which is why LSM write latency is low and stays stable under load.
  2. Flush. When the memtable reaches its size limit, the engine writes it to disk in a single sequential pass as a sorted, immutable file called an SSTable. That is the essential property: an SSTable is created once, read many times, and eventually deleted, but never edited.
  3. Compaction. SSTables accumulate, and the same key can exist in several of them with different versions. A background process merges SSTables, keeps the newest version of each key, and discards the obsolete ones. Compaction is the deferred half of the write path, run later and on the schedule the engine chooses.
The three stages of an LSM write. Stages 1 and 2 are sequential; stage 3 is the work the engine deferred.
The three stages of an LSM write. Stages 1 and 2 are sequential; stage 3 is the work the engine deferred.

The read path is where the cost returns. A row is not in one known location, so a read checks the memtable, then SSTables from newest to oldest, and merges what it finds. Consulting several files to answer a single-row read is read amplification.

To avoid opening files that cannot possibly contain the key, each SSTable carries a Bloom filter, a small structure that answers one question cheaply: is this key definitely absent from this file? A negative answer skips the file entirely. A positive answer may be a false positive, costing one unnecessary read. Bloom filters and a block cache keep LSM reads competitive, but an LSM read never reduces to the single traversal a B-tree performs.

One row, four lookups. The Bloom filter removes the files that cannot hold the key, but a positive answer still costs a file read.
One row, four lookups. The Bloom filter removes the files that cannot hold the key, but a positive answer still costs a file read.

Compaction strategy is the real engineering decision. The strategies differ in which cost they accept.

  • Leveled compaction, the RocksDB default. SSTables are organized into levels, each roughly ten times the size of the level above it, and key ranges do not overlap within a level. A read therefore touches few files and obsolete versions are cleared away quickly, so read amplification and space amplification are both low. The cost is that merging a small file into a level ten times its size rewrites a large volume of data. Write amplification of 10x is routine, and sustained load can push it past 30x.
  • Size-tiered compaction, the Cassandra default. SSTables of similar size accumulate and are merged in batches. Much less data is rewritten, so write amplification stays low, but a read may touch many overlapping files and obsolete versions survive longer, which raises read amplification and space amplification together.
  • Time-window compaction, used for time-series data in Cassandra. SSTables are grouped by time window and compacted only within their own window. When an entire window passes its retention limit, the engine deletes whole files instead of merging them, so expiry costs almost no merge work.

No strategy escapes amplification. You are choosing which of the three costs you would rather pay.

Each strategy lowers two of the three amplifications by raising the third.
Each strategy lowers two of the three amplifications by raising the third.

4. The Three Amplifications, With a Worked Number

Take 10,000 writes per second of 1 KB rows, which is 10 MB/s of logical writes.

  • A B-tree at 3x write amplification sends roughly 30 MB/s to the device, most of it random, plus the overhead of splits and fragmentation.
  • An LSM tree under leveled compaction at 10x sends roughly 100 MB/s, almost all of it sequential, plus CPU for the merges. A modern SSD absorbs 100 MB/s of sequential writes without difficulty, which is exactly why LSM engines sustain write-heavy workloads that overwhelm a B-tree. The thing to watch is that compaction competes with live reads for the same device, which is why operators throttle compaction throughput during peak hours.
The same 10 MB/s of logical writes through each engine. The byte counts favor the B-tree; the access pattern favors the LSM tree.
The same 10 MB/s of logical writes through each engine. The byte counts favor the B-tree; the access pattern favors the LSM tree.

Space amplification completes the set.

  • A B-tree gets it from fragmentation and from dead row versions waiting for vacuum.
  • An LSM tree gets it from obsolete key versions waiting for compaction.

The three quantities are not independent dials you tune separately. Reducing one raises at least one of the others, in both engine families, and seeing that is most of what separates an informed engine argument from a preference.

Crash recovery. A B-tree engine must reconcile partially written pages against its log, replaying records and checking page state before it accepts traffic. An LSM engine replays one memtable log, whose size is bounded by configuration. LSM engines therefore restart faster after a crash, and that difference becomes visible in failover time rather than in any steady-state benchmark.

5. How Each Engine Fails

  • A B-tree under write pressure saturates on random I/O, suffers bursts of page splits during bulk inserts, grows index bloat, and falls behind on autovacuum. The symptoms are write latency spikes and disk usage that climbs while the row count stays flat.
  • An LSM tree under read pressure reaches its read amplification limit: too many SSTables consulted per lookup, Bloom filters sized too small for the key count, and a block cache that cannot hold the working set. The symptom is p99 read latency climbing while write latency stays low. The fix here is operational rather than architectural: tune compaction, enlarge the Bloom filters, add cache.
  • An LSM tree under sustained write pressure reaches the opposite limit: compaction cannot keep pace with flushes, pending SSTables accumulate, and the engine pushes back until writes stall outright. Every RocksDB and Cassandra operator recognizes this graph.

You can diagnose each of these from metrics you already collect. An engine argument made without reading the amplification numbers from the running system is an argument about preferences.

6. The Senior Decision

This is a question about the workload, not a preference between products.

  • Read-heavy traffic with point lookups and range scans: choose a B-tree engine such as Postgres or MySQL.
  • High-volume append-style ingest, which covers metrics, events, logs, and most time-series data: choose an LSM engine such as Cassandra, ScyllaDB, or a RocksDB-based store.
  • Mixed, or not yet understood: choose a B-tree engine. You can scale one to very large data volumes before the engine itself becomes your constraint, its failure modes are well documented and familiar to most teams, and the operational tooling around it is deeper.

There is a general test behind all three. When somebody proposes switching engines, ask which amplification the system incurs today and which one they would prefer instead. An argument for an LSM tree that never mentions read amplification or space amplification is an incomplete argument, and an experienced interviewer will notice that immediately.

What the interviewer is scoring: this topic is a favorite deep-dive pivot. "Design a key-value store" is in practice a request to reason about LSM trade-offs. "Why is our Postgres slow on writes?" is asking for the write-ahead log, checkpoints, page splits, and bloat, roughly in that order. What separates a senior answer is quantification: "at 10,000 writes per second we are generating about 30 MB/s of random I/O, which is why the device is saturated." Expect the follow-up question "how would you reduce read amplification in your design?" and be ready to price each option: larger Bloom filters, leveled compaction, a bigger block cache, and what each one costs you in memory or in write throughput.

Flashcards Review

Write amplification

1 / 21

Reading Progress

0%

Vote for new content

On This Page

  1. Two Ways to Change a Row on Disk
  1. The B-Tree: In-Place Updates, Organized for Reads
  1. The LSM Tree: Sequential Writes, Organized for Writes
  1. The Three Amplifications, With a Worked Number
  1. How Each Engine Fails
  1. The Senior Decision