How a database actually puts bytes on disk. Two designs, one fundamental trade-off, and it explains why Postgres and Cassandra behave so differently.
Prerequisites: Computer Fundamentals, Indexing Time to read: ~24 minutes
You need to store key-value pairs on disk and retrieve them fast. Disk has one dominant property (Computer Fundamentals):
Sequential write: ~500 MB/s (SSD), ~200 MB/s (HDD)
Random write: ~50 MB/s (SSD), ~2 MB/s (HDD)
Sequential is 10–100× faster than random. Everything below follows from that one fact.
The simplest possible database:
db_set() { echo "$1,$2" >> database; } # append — sequential, fast
db_get() { grep "^$1," database | tail -1 | cut -d, -f2; } # scan everything — O(n)
Writes are as fast as physically possible. Reads are hopeless. The entire history of storage engines is about keeping fast writes while making reads acceptable — and the two answers pull in opposite directions.
The design behind almost every relational database — Postgres, MySQL/InnoDB, SQL Server, Oracle.
The idea: keep data in a balanced tree of fixed-size pages (usually 4–8 KB, matching the disk page). Each lookup follows pointers down the tree.
[ 50 | 100 ] ← root (always cached)
/ | \
[10|30] [60|80] [150|200] ← internal pages
/ | \ / | \ / | \
[..] [..] [..] ... [..] [..] ← leaf pages: the actual data
↕ ↕ ↕ ↕
(leaves linked for range scans)
📐 With ~500 keys per page, a 4-level tree indexes 500⁴ = 62 billion keys. Any lookup is 3–4 page reads, and the top levels are always in the buffer pool — so it’s typically one actual disk read.
Writing means updating in place. Find the right leaf page, modify it, write it back.
🚨 That’s a random write. And if the page is full, it splits: allocate a new page, move half the keys, update the parent (which may itself split, recursively up to the root). One logical insert can become several random writes.
A page split that’s half-finished when the machine loses power leaves a corrupted tree. So before touching any page, the database appends the intended change to a write-ahead log — sequentially.
1. Append "change X" to the WAL ← sequential, fsync'd, durable
2. Acknowledge the commit to the client
3. Modify pages in memory
4. Flush dirty pages to disk later, in the background
5. Crash? Replay the WAL from the last checkpoint
🚨 This is one of the most important mechanisms in databases, and it does much more than crash recovery:
The trade-off: every committed write is written twice (once to the WAL, once to the data pages). That’s part of B-tree write amplification.
✅ Predictable, fast reads — always 3–4 page reads, no matter how much data. ✅ Excellent range scans — leaves are linked in sorted order. ✅ Every key exists in exactly one place — so uniqueness constraints and transactional in-place updates are natural. ✅ Mature: 45 years of optimization, and every DBA understands them.
❌ Random writes — updates scatter across the disk.
❌ Write amplification — WAL + page write + page splits + every secondary index. One row insert
into a table with 5 indexes is 6+ physical writes.
❌ Fragmentation — pages end up partially full after splits and deletes, so the index is larger
than the data warrants and needs periodic maintenance (VACUUM, OPTIMIZE TABLE).
The design behind Cassandra, RocksDB, LevelDB, HBase, ScyllaDB, and (optionally) MongoDB via WiredTiger.
The idea: never update in place. Only ever append.
flowchart TB
W[Write] --> WAL[Commit log<br/>sequential append, durability]
W --> M["Memtable<br/>sorted structure in RAM"]
M -->|full → flush| L0["SSTable L0<br/>sorted, immutable file"]
L0 -->|compaction| L1[SSTable L1]
L1 -->|compaction| L2[SSTable L2 …]
The write path:
🚨 Every disk write is sequential. That’s the whole point, and it’s why LSM-trees can absorb enormous write throughput on cheap hardware.
Deletes are interesting. You can’t delete from an immutable file, so you write a tombstone — a marker saying “this key is deleted.” The real removal happens during compaction.
⚖️ This causes a genuine operational problem: a workload that writes and deletes heavily accumulates tombstones, and reads must scan past them. Cassandra users regularly hit “too many tombstones” errors on queue-like workloads. LSM-trees are a poor fit for use-as-a-queue patterns, and knowing that is a good practical signal.
A key might be in the memtable, or in any SSTable. A naive read checks all of them.
Three optimizations make it viable:
📐 Even so, a read may touch several files. LSM reads are slower and less predictable than B-tree reads, especially for keys that don’t exist (every Bloom filter must be consulted).
The background merging is where LSM-tree tuning lives:
| Strategy | How | Trade-off |
|---|---|---|
| Size-tiered (STCS) | Merge SSTables of similar size | Write-friendly; needs up to 50% free disk during compaction; worse read amplification |
| Leveled (LCS) | Keep non-overlapping SSTables per level | Read-friendly, predictable space; much more write amplification |
| Time-window (TWCS) | Group by time window | Ideal for time-series with TTL — whole SSTables expire at once |
🚨 Compaction is not free, and it’s the most common operational surprise with LSM engines. It consumes CPU, disk I/O, and disk space in the background — and it competes with your live traffic. Latency spikes during compaction are a well-known phenomenon. Sizing disk at 2× your data for size-tiered compaction is a real requirement, not a suggestion.
✅ Extremely high write throughput — everything is sequential. ✅ Better compression — SSTables are immutable and sorted, so they compress well and stay compressed. ✅ No fragmentation — compaction continuously rewrites into dense files. ✅ Smaller on disk than an equivalent B-tree, typically.
❌ Reads touch multiple files — slower and more variable. ❌ Compaction competes with live traffic — latency spikes, CPU and I/O cost. ❌ Space amplification — obsolete data lingers until compacted. ❌ Tombstones accumulate on delete-heavy workloads.
| B-tree | LSM-tree | |
|---|---|---|
| Writes | Random, in-place | Sequential, append-only |
| Write throughput | Good | Excellent |
| Read latency | Predictable, ~1 disk read | Variable, may touch several files |
| Range scans | Excellent | Good |
| Write amplification | Moderate (WAL + pages + indexes) | Moderate–high (compaction rewrites data repeatedly) |
| Space amplification | Fragmentation | Obsolete data pending compaction |
| Compression | Poorer (in-place pages) | Better |
| Background work | VACUUM / defragmentation |
Compaction (significant) |
| Transactions | Natural | Harder (data in many places) |
| Used by | Postgres, MySQL, SQL Server, Oracle | Cassandra, RocksDB, LevelDB, HBase, ScyllaDB |
🎙️ The one-line summary worth memorizing: “B-trees optimize reads by paying for random writes; LSM-trees optimize writes by paying for complex reads and background compaction.”
A useful framework — every storage engine trades between these, and you cannot minimize all three:
| Definition | B-tree | LSM | |
|---|---|---|---|
| Read amplification | Disk reads per logical read | Low (~1) | Higher (several SSTables) |
| Write amplification | Bytes written per logical byte | Moderate | Higher (compaction rewrites repeatedly) |
| Space amplification | Disk used per logical byte | Fragmentation (~1.3×) | Obsolete data (up to 2×) |
🚨 This is the RUM conjecture (Read, Update, Memory): you can optimize for at most two. It’s a genuinely useful frame for any storage discussion, and mentioning it signals real depth.
Choose a B-tree engine (Postgres, MySQL) when:
Choose an LSM engine (Cassandra, RocksDB) when:
📐 The crossover point is higher than people assume. A tuned Postgres on modern NVMe handles tens of thousands of writes/second. Reaching for Cassandra at 2,000 writes/second is choosing operational complexity you don’t need.
🎙️ “This is write-heavy — 100,000 inserts per second of append-only event data with known access patterns. That’s the LSM case, so Cassandra. If it were 5,000 writes/second with ad-hoc queries, I’d stay on Postgres.”
Column-oriented storage. Store all values of one column together rather than all fields of one row. Analytical queries touching 3 of 50 columns read 6% of the data instead of 100%, and columns of the same type compress spectacularly (10–100×). This is why analytics databases exist — ClickHouse, Redshift, BigQuery, DuckDB, Parquet. → Analytics Storage
Row vs column in one line: rows for OLTP (“give me everything about order 42”), columns for OLAP (“average order value by month across 2 billion orders”).
In-memory engines (Redis, SAP HANA) skip the disk problem entirely, at RAM prices.
Hash indexes (Bitcask) — an in-memory hash map of key → file offset. Extremely fast, but the key set must fit in RAM and range queries are impossible.
Fractal trees / B-ε trees (TokuDB) buffer writes in internal nodes — a hybrid that improves B-tree write performance.
| Decision | Gain | Cost |
|---|---|---|
| B-tree | Predictable fast reads, transactions, range scans | Random writes, fragmentation, write amplification |
| LSM-tree | Huge write throughput, better compression | Slower/variable reads, compaction overhead, tombstones |
| Leveled compaction | Better reads, bounded space | More write amplification |
| Size-tiered compaction | Cheaper writes | Up to 2× disk space needed; worse reads |
| Column store | 10–100× faster analytics, great compression | Terrible for single-row reads and updates |
| Larger memtable | Fewer flushes, better batching | More data lost on crash (replayed from log), more RAM |
VACUUM is the B-tree equivalent of compaction — reclaiming space from dead tuples.
“We forgot to tune autovacuum” is behind a large share of Postgres performance incidents, and
transaction ID wraparound is a genuinely scary failure mode worth reading about.1. Watch write amplification. In Postgres, insert 1 million rows into a table with 0 indexes,
then 5 indexes. Compare insert time and check pg_stat_wal for bytes written. The WAL volume
difference is the amplification, made visible.
2. Watch compaction happen. Run Cassandra in Docker, write a few million rows, then:
nodetool tablestats keyspace.table # SSTable count, space used
nodetool compact keyspace table # force compaction
nodetool tablestats keyspace.table # watch the file count collapse
Monitor CPU and disk I/O during the compaction. That’s the background cost.
3. Cause the tombstone problem. In Cassandra, insert 100,000 rows into a partition, delete 99,000 of them, then query the partition. Watch the read get slow and eventually warn about tombstones. This is the “don’t use Cassandra as a queue” lesson, demonstrated in five minutes.
4. Feel the sequential/random difference directly.
# Sequential write
dd if=/dev/zero of=seq.bin bs=1M count=1000 oflag=direct
# Random write
fio --name=rand --rw=randwrite --bs=4k --size=1G --direct=1
The ratio you measure is the reason both of these designs exist.