Reads and writes: how databases store and fetch data

A storage engine turns “insert this row” and “find that row” into reads and writes on a disk. Almost every engine uses one of two designs: a B-tree that updates fixed-size pages in place, with a log for safety (PostgreSQL, InnoDB, SQLite), or a log-structured merge-tree (LSM) that only appends and sorts in the background (RocksDB, Cassandra, HBase). Each is fast at something because it pays somewhere else, and knowing where explains most production surprises.

Picture it first: two parcel offices

Two railway parcel offices each take thousands of parcels a day and must hand any one back on request.

The shelf office puts every parcel straight into its labelled slot, so finding one is instant. But every arrival means a walk to some random shelf, so the clerk first jots each arrival in a day-book by the door, in case the lights go out mid-walk.

The tray office notes each arrival in the day-book and drops it in an in-tray. A full tray is sorted into one box, and every night staff merge the boxes into big sorted cartons. Arrivals are fast; a lookup checks the tray, then the boxes newest first, unless an index card says “not in this box”; and the nightly merging cannot be skipped.

Map it back: the shelves are a B-tree, the day-book is the write-ahead log, the tray is a memtable, the boxes are SSTables, the merging is compaction, and the index cards are Bloom filters.

The numbers that drive the design

Two facts shape every engine: memory is tens of thousands of times faster than storage, and storage prefers large sequential transfers to small random ones.

So a page that misses memory on gp3 costs at least 1 ms / 100 ns = 10,000× one that hits. Random I/O also wastes bandwidth: at 3,000 IOPS, random 8 KiB pages move only 3,000 × 8 KiB ≈ 23 MiB/s, under a fifth of gp3’s 125 MiB/s. On a spinning disk, one 8 ms seek costs as much as reading 400 KB sequentially (Norvig puts 1 MB at 20 ms).

Engines respond in two ways. They move data in pages (8 KB in PostgreSQL, 16 KB by default in InnoDB) and cache hot pages in a buffer pool in RAM. And they turn random writes into sequential appends: the log in a B-tree engine, everything in an LSM.

The B-tree write path

PostgreSQL and InnoDB store tables and indexes as B-trees of pages, and at commit they never write a changed page to its home on disk. They follow the write-ahead logging rule: log first, data later.

1. Change the page in memory. The page is read into the buffer pool if needed, changed there and marked dirty. In PostgreSQL, MVCC makes the change a new row version, not an overwrite.
2. Log the change. A small record, often around a hundred bytes, goes into the WAL buffer.
3. At COMMIT, fsync the log. This is the only disk wait on the commit path, and it is sequential. Group commit amortises it: one fsync makes every commit record written so far durable, so concurrent commits share a flush. PostgreSQL’s commit_delay can even wait a few microseconds to gather more.
4. Acknowledge. The commit is durable although no table page has reached disk.
5. Write dirty pages back later. PostgreSQL’s background writer and checkpointer, and InnoDB’s page cleaners, flush dirty pages in the background. After a checkpoint, every earlier change is on disk, so crash recovery replays WAL only from there. PostgreSQL checkpoints every 5 minutes or 1 GB of WAL by default and spreads the writes over 90% of the interval.

Torn pages: why pages get written twice

Storage writes 512-byte or 4 KB sectors, but a page is 8 or 16 KB. A power cut mid-write leaves the page torn, part new and part old, and a small log record cannot repair it. Both engines pay to prevent this:

• PostgreSQL full-page writes. The first change to a page after a checkpoint puts the whole page image into the WAL, so recovery can rebuild it. More frequent checkpoints mean more of these images.
• InnoDB’s doublewrite buffer. Pages are first written to a doublewrite area in one large sequential chunk with one fsync, then to their home locations; after a crash, InnoDB takes the good copy. Data is written twice, but not with twice the I/O operations.

The B-tree read path

A read walks the B-tree from the root to a leaf, looking up each page in the buffer pool first. A hit costs a memory access; a miss costs a storage read and may evict another page. The root and internal levels are touched by every query and almost never leave memory, so leaves and table pages decide your latency.

Hit ratios hide how much a miss matters. With a 1 ms miss, a 99% hit ratio averages 0.01 × 1 ms = 10 µs per page and 99.9% averages 1 µs. The last 1% of misses sets the speed, which is why “the working set fits in memory” is the key sentence in database capacity planning.

The two engines size that memory differently:

• PostgreSQL reads through the OS page cache, so a page can be cached twice. shared_buffers defaults to 128 MB; the docs suggest 25% of RAM on a dedicated server and doubt that more than 40% helps, since the OS cache does the rest.
• InnoDB bypasses the OS cache with O_DIRECT by default on Linux, so its buffer pool (also 128 MB by default) is the only cache and often gets up to 80% of RAM. New pages enter its LRU list at a midpoint, with 3/8 of the pool as the “old” sublist, so one big scan cannot flush out the hot pages.

Engines also read ahead: InnoDB fetches the next 64-page extent once 56 pages of the current one were read in order, and PostgreSQL 18 issues asynchronous reads that combine neighbouring pages into requests of up to 128 kB. That is why a sequential scan can beat an index per row, as index scan vs full table scan explains.

The LSM write path

Patrick O’Neil and colleagues proposed the log-structured merge-tree in 1996 for a table with a high insert rate, where keeping a B-tree index current would roughly double each transaction’s I/O. Their answer: batch changes in memory and cascade them to disk in sorted runs, like a merge sort. Google’s Bigtable (2006) gave the design its modern vocabulary; LevelDB, RocksDB, Cassandra, ScyllaDB and HBase follow it.

1. Append to the commit log (RocksDB calls it the WAL) so the write survives a crash.
2. Insert into the memtable, a sorted in-memory structure (RocksDB’s default is a skiplist of 64 MB). The write is done. Nothing on disk was read or modified in place.
3. Freeze the full memtable; it becomes read-only and a fresh one takes new writes.
4. Flush it to disk as an immutable, sorted file: an SSTable (sorted string table). Bigtable calls this a minor compaction. Duplicate updates to one key are collapsed on the way out.
5. Compact in the background: merge SSTables into larger sorted runs, dropping overwritten values.

Deletes are writes too. Since files are immutable, a delete writes a tombstone, a marker that hides older values of the key. Compaction drops the hidden values when it merges them with the tombstone, and drops the tombstone itself only at the bottom level, where nothing older can remain. Cassandra keeps tombstones for a grace period, gc_grace_seconds, of 10 days by default, so a replica that was down during the delete cannot bring the row back as a “zombie” during repair.

The LSM read path

A point read wants the newest version of a key, so it searches newest to oldest: memtables, then every L0 file (they overlap), then each lower level. Three structures keep that cheap:

• Fence pointers. Below L0, each level is one sorted run split into files with known key ranges, so a binary search picks at most one file per level; inside it, an index block points to the right data block (4 KB by default in RocksDB).
• Bloom filters. Each SSTable’s in-memory filter answers “definitely not here” for most files; at RocksDB’s 10 bits per key, about 1% false positives (the maths is in Bloom filters).
• Block cache. Hot data, index and filter blocks stay in memory. RocksDB’s default is only 32 MB, so production systems set it far higher.

Range scans are where LSMs pay. A filter answers questions about one key, not a range, so a scan must merge iterators over every sorted run that might overlap it. RocksDB’s guide puts read amplification for a short range scan at the number of L0 files plus the number of non-empty levels.

Compaction: leveled or size-tiered

Compaction decides how many sorted runs exist, so it decides the LSM’s costs. There are two families.

Leveled compaction (RocksDB’s default) keeps each level below L0 as a single sorted run, about 10× larger than the one above. When a level exceeds its target, one file merges with the overlapping files below. RocksDB’s tuning guide works a 500 GB example with a 512 MB L1: L2 is 5 GB, L3 51 GB and L4 512 GB. Space amplification is only (0.5 + 0.5 + 5 + 51 + 512) GB / 500 GB ≈ 1.14. But each byte is written once into L0, about twice in the L0→L1 merge and about 10 times at each later level, merged with ten times as much data below: 1 + 2 + 10 + 10 + 10 ≈ 33× write amplification.

Size-tiered compaction (Cassandra’s default, and RocksDB’s “universal” style) waits for several runs of similar size, then merges them into one bigger run. Each byte is rewritten far fewer times. You pay on the other axes: more runs per read, spikier compaction I/O, and big merges that can temporarily double the space used. Cassandra recommends its leveled strategy for read-heavy tables and tables with many updates and deletes.

Read, write and space amplification

The RUM conjecture of Manos Athanassoulis and colleagues (2016) frames the design space with three overheads: read amplification (data read per byte wanted), write amplification (bytes written to storage per byte changed) and space amplification (bytes stored per byte of live data). Optimise any two and the third gets worse. Roughly, a B-tree favours reads, a leveled LSM trades some read cost for writes and space, and a size-tiered LSM favours writes above all.

Write amplification is where the two families differ most, and the arithmetic is worth doing once. Change one 100-byte row:

• PostgreSQL, cold page: 100 bytes of WAL, a full-page image of up to 8 KB (first change since the checkpoint), then the 8 KB page: about 16 KB, 161×.
• InnoDB, cold page: 100 bytes of redo, the 16 KB page into the doublewrite area, then in place: about 32 KB, 321×.
• RocksDB, leveled: the WAL record plus about 33 rewrites by compaction: about 3.4 KB, 34×, all sequential.
• PostgreSQL, hot page: 100 changes share one page image and one flush, (100 × 0.1 + 8 + 8) KB / 100 ≈ 0.26 KB each: about 2.6×.

That last line is the key insight. A B-tree’s write cost depends on locality: appends and hot spots amortise well, while random updates across a table far larger than memory get the worst case. An LSM’s cost is roughly constant per byte and paid in big sequential writes, which flash handles well and which wear it less. Every secondary index multiplies the B-tree side, as the Uber story below and HOT updates in indexes in practice show.

B-tree or LSM?

Choose a B-tree when reads, range scans, transactions and predictable latency matter most: most OLTP systems of record. Choose an LSM for write-heavy or time-ordered data, large datasets on flash, and as the local engine of distributed databases (CockroachDB uses Pebble, a Go engine inspired by RocksDB).

Both are row stores: a page holds whole rows, ideal for fetching one order. Analytical engines store each column separately, so a query reading 3 of 100 columns touches 3% of the bytes; see OLTP vs OLAP.

Durability knobs and what they cost

Every engine lets you skip the fsync wait for speed. Know exactly what each setting loses.

Going deeper: failure modes and war stories

Checkpoint spikes

Say 4 GB of a 16 GB shared_buffers is dirty when a checkpoint starts. Spread over 90% of 5 minutes, that is 4,096 MB / 270 s ≈ 15 MB/s. If max_wal_size is too small for a write burst, checkpoints come every minute instead: 4,096 MB / 54 s ≈ 76 MB/s, over half of gp3’s 125 MiB/s, plus a fresh wave of full-page images. PostgreSQL logs a warning when checkpoints come closer than checkpoint_warning (30 s); the usual fix is a larger max_wal_size.

Compaction falls behind

An LSM can accept writes faster than it compacts them for a while, then pays. RocksDB stalls writes when too many memtables wait to flush, too many L0 files pile up, or estimated pending compaction bytes grow too large: first it slows every write, then stops them, and a stall in one column family stalls the whole database. CockroachDB calls the same debt an inverted LSM: more data in upper levels than lower ones, so reads wade through many small files. The fixes are more compaction threads, larger memtables and, above all, disk bandwidth for compaction, about 30× the user write rate on a leveled LSM.

Tombstones that never go away

A queue-like Cassandra table, where rows are inserted, read once and deleted, piles up tombstones that reads must scan past. Cassandra warns at 1,000 tombstones in one query and fails it at 100,000. Model such data with time-bucketed partitions you can drop whole, or use a real message queue.

A buffer pool that is too small

When the working set outgrows memory, the hit ratio slips from 99.9% to 99% and average page cost rises tenfold with no code change. Watch hit ratios and IOPS, not just CPU.

Uber, 2016: write amplification in the wild

Uber explained its move from PostgreSQL to MySQL largely by write amplification. In PostgreSQL 9.2, updating one indexed column wrote a new row version plus a new entry in every index, because each index pointed at the physical row; with a dozen indexes, a one-field change touched all twelve. All of it went into the WAL, and since replication shipped those physical changes, cross-data-centre bandwidth and WAL archiving struggled at peak. InnoDB’s secondary indexes point at the primary key, so unrelated indexes are untouched. (PostgreSQL’s HOT updates skip index writes only when no indexed column changes.) Read it as a lesson in counting writes per update, not a verdict on either database.

Meta, 2016: MyRocks halves the user database

Meta moved its MySQL user database tier from compressed InnoDB to MyRocks, a RocksDB engine for MySQL, and used 50% less storage. The reasons were engine details: a 16 KB InnoDB page compressed to 5 KB still occupies an 8 KB slot, every InnoDB row carries 13 bytes of uncompressed transaction metadata, and the doublewrite buffer writes pages twice. In their benchmark, MyRocks was 3.5× smaller than uncompressed InnoDB and wrote orders of magnitude fewer bytes.

Cheat sheet

How to say it in the interview

“I pick the storage engine by the read/write mix. PostgreSQL and InnoDB are B-trees: a commit fsyncs a small WAL record, the changed page stays dirty in the buffer pool and a checkpoint writes it back, so reads and range scans are fast and predictable, but random updates rewrite whole 8 or 16 KB pages, once per index. An LSM like RocksDB or Cassandra appends to a log and a memtable, flushes sorted immutable files and compacts them in the background, so writes are cheap and sequential while reads lean on Bloom filters. For this write-heavy event store I’d use an LSM with leveled compaction and budget about 30× the ingest rate in compaction I/O; orders stay in PostgreSQL with the working set in memory.”

Why are B-trees better for reads and LSMs better for writes? A B-tree keeps one sorted copy, so a read follows one path, but every write must land on that path at a random page. An LSM writes new files sequentially and defers the sorting, so a read consults several files until compaction catches up.

What is write amplification, and how do you cut it? Bytes written to storage per byte changed. In a B-tree: fewer indexes, HOT-friendly updates, longer checkpoint intervals, better locality. In an LSM: larger memtables or tiered compaction, paid for in read or space amplification.

Your Cassandra or RocksDB writes suddenly slow down. What is happening? Usually compaction debt: L0 files or pending compaction bytes crossed the stall thresholds, so the engine throttles writes until compaction catches up. Check disk throughput, compaction threads and write bursts, and tombstone-heavy partitions if reads are slow too.

Is synchronous_commit = off safe? Safe from corruption, not from loss: after a crash you can lose up to about 600 ms of acknowledged commits. Fine for regenerable data, wrong for money.

Where to go next

• Write-ahead logging: the log-first rule, recovery and replication from the WAL.
• Database indexes: B+tree structure and height, the base of the B-tree engine.
• Indexes in practice: HOT updates, bloat and UUIDv7, the B-tree write costs in production.
• MVCC and vacuum and bloat: why PostgreSQL updates create row versions and how they are cleaned up.
• Bloom filters: the maths behind the LSM read path.
• Cassandra and DynamoDB: LSM-based databases in a design.
• OLTP vs OLAP: column stores and why analytics flips the layout.
• Design a key-value store: an LSM engine inside a full distributed design.

References and further reading

1. PostgreSQL documentation: WAL configurationpostgresql.orgCheckpoints every 5 minutes or 1 GB of WAL by default, checkpoint_completion_target 0.9, and why shorter intervals add full-page writes.
2. PostgreSQL documentation: write-ahead log settingspostgresql.orgsynchronous_commit and its 3 × wal_writer_delay loss window, commit_delay for group commit, and full_page_writes against torn pages.
3. MySQL 8.4 Reference Manual: InnoDB startup options and system variablesdev.mysql.com16 KB default page size, 128 MB default buffer pool, innodb_flush_log_at_trx_commit 0/1/2, O_DIRECT, linear read-ahead and the old-sublist share of the LRU.
4. MySQL 8.4 Reference Manual: doublewrite bufferdev.mysql.comWhy InnoDB writes flushed pages twice, and why that costs one large sequential write rather than twice the I/O operations.
5. RocksDB wiki: tuning guidegithub.comDefinitions of read, write and space amplification, the 500 GB leveled example (write amplification ≈ 33, space ≈ 1.14), universal compaction’s temporary 2× space, and filter and block defaults.
6. RocksDB wiki: write stallsgithub.comThe three stall triggers (memtables, L0 files, pending compaction bytes) and how a stall slows or stops the whole database.
7. The Log-Structured Merge-Tree (O’Neil, Cheng, Gawlick and O’Neil, Acta Informatica, 1996)cs.umb.eduThe original LSM-tree: deferring and batching index changes from a memory component into disk components, like a merge sort.
8. Bigtable: A Distributed Storage System for Structured Data (Chang et al., OSDI 2006)static.googleusercontent.comCommit log, memtable and SSTables; minor, merging and major compactions; deletion entries; per-SSTable Bloom filters.
9. Why Uber Engineering Switched from Postgres to MySQL (Uber Engineering, 2016)uber.comWrite amplification across secondary indexes and its knock-on effect on WAL replication bandwidth, on PostgreSQL 9.2.
10. MyRocks: A space- and write-optimized MySQL database (Meta Engineering, 2016)engineering.fb.comMoving the user database tier from compressed InnoDB to RocksDB: 50% less storage, and the page-alignment and metadata reasons behind it.