Cruxly › System design › Databases: Choosing One

Storage engines: B-trees, LSM-trees, row vs column

the engine under the database decides which workloads it can survive

Every database choice you defend in an interview is really a storage-engine choice in disguise. A B-tree, an LSM-tree and a column store each make one kind of work cheap by making another kind expensive, and the names for those costs are read, write and space amplification.

Three amplifications: the vocabulary of every engine comparison

"B-trees read faster, LSM-trees write faster" is true and nearly useless. Staff-level answers use three measurable quantities. RocksDB's tuning guide defines them:

• Write amplification: bytes written to storage per byte the user wrote. If your disk absorbs 30 MB/s while the application writes 10 MB/s, write amplification is 3.
• Read amplification: how many places (pages, files) one query has to read.
• Space amplification: bytes on disk divided by bytes of live data.

Tuning one usually worsens another. That tension is the whole subject.

The 80x figure is arithmetic (8,192 / 100), not a benchmark. Real engines amortise it, because many updates to the same hot page share one flush. The shape is what matters: a B-tree pays per page, an LSM pays per compaction.

:::key Say "amplification", not "fast" or "slow" "This workload is write-heavy with small rows, so write amplification dominates. A leveled LSM can pay tens of times in compaction I/O (the RocksDB tuning guide's five-level example is about 33). A size-tiered one pays less write amp but more space and more read work." That sentence shows you know what you are trading. :::

B-trees in practice: pages, splits and fill factor

You saw the shape in the indexing lesson. Here is what decides the cost in production.

Pages. Postgres uses 8 KB pages and InnoDB 16 KB by default (set at instance initialisation in MySQL, so it cannot change later). Internal pages hold keys and child pointers. If an entry takes about 16 bytes, a 16 KB internal page fans out roughly a thousand ways, so a billion-row table needs three to four levels. That is arithmetic with a made-up entry size; real fan-out varies with key width.

Splits. When a leaf cannot fit a new entry, it splits and a new downlink goes into the parent. The parent can split too, so splits cascade upward, and a root split adds a level (Postgres docs). Each split is a write to pages that can be anywhere on disk.

Fill factor controls how much room pages keep for future inserts.

Why key choice matters. In InnoDB the table is the clustered index, normally the primary key (a hidden row ID if none is defined), so rows live in the leaves. A random key (a v4 UUID) sends every insert to a different leaf: all leaves fill together, split together, and settle half empty. That means more pages to cache, more random writes and a bigger index. A time-ordered key appends at the right edge and leaves old pages dense. Its cost moves to the hot right edge: every insert targets one page.

Updates cause splits too. In Postgres, an update that is not HOT (heap-only tuple) writes a new entry in every index. Update-heavy tables create version churn, and Postgres 14 added bottom-up deletion, which removes expired index entries from a leaf to prevent a split (it targets indexes whose keys the UPDATE did not change). You still need vacuum for full cleanup.

Interview follow-up: "Why does a random UUID primary key hurt on MySQL?" Because the rows themselves are stored in primary-key order. Random keys scatter inserts across the whole table, splitting pages everywhere. Sequential or time-ordered ids append to one edge.

The write-ahead log and checkpoints: how in-place engines survive crashes

In-place updates are dangerous. If the machine dies mid-write, the page on disk is wrong. Every B-tree engine therefore follows one rule: the log record reaches stable storage before the changed page is written. By default a commit is also acknowledged only after that log flush, though most engines let you relax this (see the list further down).

A commit, step by step

1. Change the page in the buffer pool (memory). It is now dirty.
2. Append a log record to the write-ahead log (WAL). This is a sequential write.
3. Flush the log to stable storage. Databases let several commits share one flush (group commit).
4. Acknowledge the client.
5. Write the dirty page to the data file later, in the background.

Checkpoints bound recovery. Postgres defaults: a checkpoint at least every 5 minutes (checkpoint_timeout), sooner if WAL nears max_wal_size (1 GB, a soft limit), with writes spread across 90% of the interval (checkpoint_completion_target). Crash recovery replays WAL from the last checkpoint, so a longer interval means longer recovery. MongoDB's WiredTiger also pairs a journal (for changes between checkpoints) with a checkpoint every 60 seconds, but it writes checkpoints to new locations instead of overwriting pages, so the torn-page problem below is not its problem.

Torn pages. A page write can be interrupted halfway. Postgres writes 8 KB at a time while disk sectors are commonly 512 bytes (16 sectors per page), so a crash can leave a mix of old and new data, and a small log record cannot repair a half-written page. Postgres, with full_page_writes on by default, puts a full page image in the WAL on the first change after each checkpoint. InnoDB writes flushed pages to a doublewrite buffer first, as one large sequential chunk with a single fsync, so recovery finds a good copy. Both add write amplification. Postgres's full-page images also mean a more frequent checkpoint raises WAL volume (the Postgres docs suggest a longer checkpoint interval to reduce it); InnoDB's doublewrite buffer is separate from the redo log and does not.

How "committed" data gets lost on a healthy database

• Postgres synchronous_commit = off reports success before the WAL flush. You can lose up to three times wal_writer_delay of recent commits (about 600 ms by default) but the database is not corrupted. It can be set per transaction.
• Turning fsync off can corrupt the database.
• Other engines relax the ack-after-flush rule too: a MongoDB write with w:1 and no j:true is acknowledged before the journal flush (the journal is flushed every 100 ms by default), and InnoDB's innodb_flush_log_at_trx_commit set to 0 or 2 does not flush the redo log at every commit.
• A disk or controller write cache that lies about flushes.
• A single node losing its disk. Durable on one node is not durable across node loss; that needs replica acknowledgement.

:::key Trap: "durable means it hit the disk" Only if the log was flushed, the device honours the flush, and you do not need to survive losing the machine. :::

LSM-trees: levels, memtables and bloom filters

The earlier lesson showed the memtable, WAL and SSTables. Here is the part that decides real behaviour: levels.

The write path. A write goes to the WAL and the memtable. A full memtable becomes immutable and a background thread flushes it to an SSTable while a fresh memtable takes new writes. No write seeks to old data, so writes are sequential.

Levels (leveled compaction, as in RocksDB and CockroachDB's Pebble).

• New files land in L0. L0 is the one level whose files may overlap in key range.
• L1 and deeper keep files that do not overlap, so a key has at most one candidate file per level.
• Each level targets about 10x the data of the one above. About 90% of data ends up in the last level.
• Compaction picks the level with the highest score (size over target size), merges a file with the overlapping range of the next level, writes new files and deletes the old ones.

That 10x fan-out is why leveled write amplification is high: a byte is rewritten as it moves down each level. The RocksDB tuning guide's five-level example works out at 1 + 2 + 10 + 10 + 10 = 33.

The read path. Check the memtable, then every L0 file, then one file per deeper level. Pebble's docs treat a read amplification below 10 as healthy and warn that an inverted LSM (more data in a higher level than the one below, because compaction is behind) degrades reads.

Bloom filters. Each file carries a filter that answers "definitely not here" or "maybe". RocksDB's guidance: about 10 bits per key gives a 1% false-positive rate, and about 15.5 bits per key gives 0.1%. Cassandra exposes the same trade-off as the table option bloom_filter_fp_chance (its documentation notes that 0.01 needs about three times the memory of 0.1); the default differs by compaction strategy and version, so check the docs for yours. Two limits to say aloud:

• Whole-key filters help point lookups only. A range scan needs prefix filters (RocksDB needs a prefix extractor configured), otherwise it consults every level.
• Filters cost memory. The trade is RAM for fewer disk reads.

Deletes write a tombstone, not an erasure. Space returns only when compaction reaches the data.

Compaction strategies and write stalls

Compaction strategy is the knob that moves you between the three amplifications. Pick it per workload.

TWCS wins on retention because expired windows are dropped as whole files, with no rewrite. Cassandra's docs suggest choosing a window that yields about 20-30 windows, so a 90-day TTL fits 3-day windows. Cassandra 5.0's docs also recommend the newer Unified Compaction Strategy for most new workloads.

Write stalls. When compaction cannot keep up, RocksDB deliberately throttles writes. It slows or stops writes when (1) the number of memtables waiting to flush reaches max_write_buffer_number (a full stop), (2) L0 files reach the slowdown trigger and then the stop trigger, or (3) pending compaction bytes pass the soft and then the hard limit. It cuts the write rate to delayed_write_rate and may go lower while the backlog grows. Limits are per column family, but a stall hits the whole database. CockroachDB tells operators the same story: too little compaction lets L0 grow and read amplification rise.

What you do about p99 spikes on an LSM store

• Confirm the cause: compaction backlog, L0 file count, read amplification.
• Add compaction capacity (disk bandwidth, concurrency) or smooth the write burst upstream.
• Switch strategy: tiered for write-heavy, leveled for read-heavy, time-window for TTL data.
• Large values: Pebble documents optional value separation, which cuts write amp by about 50% at the cost of about 20% space amp.

:::warn "Cassandra uses leveled compaction by default" is wrong STCS is the default. Naming the default correctly is a cheap way to show you operated one. :::

Row stores versus column stores

Everything so far assumed a row is stored together. A column store inverts that.

Why columns scan faster. A query like SUM(amount) GROUP BY country needs two columns. A column store reads those two and skips the rest. Values in one column share a type and often repeat, so they compress better. DuckDB's docs describe a vectorised engine that processes batches of values at once instead of one row at a time. I am not giving you a speedup multiplier, because it depends entirely on how many columns you skip and how compressible they are; measure on your own table.

How real columnar systems store data

• Parquet: a file holds row groups; each row group has one contiguous column chunk per column, split into pages.
• ClickHouse (MergeTree): each insert creates an immutable part sorted by the primary key, and background merges combine parts, which is the LSM idea in column form. Wide parts store each column in its own file. The index is sparse: one entry per granule of 8,192 rows by default, and the primary key is not unique. Point lookups are weak by design.
• DuckDB: embedded, columnar, vectorised, aimed at analytics, with ACID via MVCC.

What they are bad at. Single-row updates and high-rate point writes. ClickHouse's docs call ALTER TABLE ... UPDATE a heavy operation (a mutation that rewrites parts) not designed for frequent use. Its newer lightweight UPDATE writes patch parts instead and suits small, frequent updates (up to about 10% of a table), at the price of extra work on every SELECT, and patch parts count toward part limits. Neither makes it an OLTP engine. Also, inserts should be batched, because every insert makes a part.

HTAP means serving both. TiDB keeps rows in TiKV (RocksDB underneath) and adds TiFlash, a columnar replica that joins each Raft group as a non-voting learner. Replication is asynchronous and does not block TiKV writes, and PingCAP says TiFlash reads still return the latest committed data (Snapshot Isolation, validated through the Raft index). So you pay with a second copy of the data and extra replication work, and a read may wait for the learner to catch up. A separately fed warehouse (a CDC pipeline) does lag.

:::key The one-line OLTP versus OLAP test Does the query touch few rows, all columns (row store) or many rows, few columns (column store)? :::

From engine to workload, and how to say it in an interview

Which popular systems use which engine (per each project's documentation):

Note Postgres stores rows in an unordered heap with indexes pointing at tuple IDs, while InnoDB's table is its clustered B-tree, normally on the primary key. Same family, different behaviour on random keys.

How to say it in an interview (30 seconds):

1. Name the access pattern: reads or writes, point or scan, row size, update rate.
2. Name the engine that fits and one amplification you accept.
3. Name the operational failure mode: page splits and bloat for B-trees, compaction stalls for LSM, small inserts or updates for column stores.
4. Offer the mixed answer if asked: a transactional store plus an analytical replica.

Follow-ups to expect

How to say it in the interview

"Before I pick a database I pick an engine, because the engine sets the ceiling. Point reads and in-place updates with transactions point me at a B-tree store like Postgres or MySQL. A sustained write firehose points me at an LSM store, and I would say which compaction strategy and what happens to p99 when compaction falls behind. Big scans and aggregates point me at a column store. Then I name the amplification I am choosing to pay."

Checklist

• Described the choice in write, read and space amplification, not fast or slow
• Explained a page split, fill factor and why random keys bloat a B-tree
• Walked a commit through WAL, flush, ack, dirty page and checkpoint
• Explained LSM levels, bloom filters and what they cannot help (range scans)
• Chose a compaction strategy for the workload and named its failure mode
• Said what causes write stalls and how I would diagnose a p99 spike
• Matched row versus column storage to OLTP versus OLAP, and proposed two engines for mixed loads

Related lessons

• How to choose a database
• ACID, precisely
• Isolation levels, in depth
• Data models: what each family is built for, and where it fails
• NoSQL modelling in practice: DynamoDB, Cassandra, MongoDB
• Distributed SQL: Spanner, CockroachDB, Aurora and friends