Loading...
Loading...
How databases physically store and retrieve data — storage engine internals
The previous topic ended on concrete arithmetic: 100 million order rows near 200 bytes each need about 20 GB of heap, which is the storage holding the actual row data, plus 10 to 15 GB of indexes, and the working set stays in the buffer pool, which is the memory cache for hot pages, so indexed lookups answer in single-digit milliseconds. That math tells you the data fits, but not why a lookup costs three page hops instead of a full scan, or why pushing to a billion rows turns vacuuming, which is reclaiming space from dead row versions, into an hours-long job. The storage engine, which is the code deciding how bytes are laid out on disk and memory, sets that floor. One family of engines organizes data in sorted trees that favor disk-friendly reads and ordered scans, while the other buffers writes in memory and merges them later to avoid seeks during ingestion. That layout choice ripples into write amplification, which is how many bytes are physically written per byte the user changed, background merging work, and even how far replicas lag.
Buying hardware first without understanding the layout fails because each engine bottlenecks somewhere different: one stalls on random writes, the other on background merges and multi-file reads. A team that doubles RAM from 64 GB to 128 GB to fix a 10-millisecond 99th percentile on an LSM store with 40 overlapping files at the youngest level buys nothing, because each cold read still probes dozens of files and the tail stays near 30 milliseconds until merging catches up. Think of a mailroom that either files each letter immediately into labeled cabinets or tosses arrivals into dated bins and sorts the bins overnight: one analogy for the whole idea, where cabinets favor finding one letter fast and bins favor absorbing a flood without walking to the cabinets each time.
| Engine family | Write cost | Point read | Range scan | Systems built on it |
|---|---|---|---|---|
| B+ tree, the cabinet engine with sorted pages | In-place page update with a random write per edit | A few page reads, fast when cached | Excellent, because leaf pages link sequentially | PostgreSQL, which is the leading open-source relational database, and MySQL InnoDB, its widespread storage backend |
| LSM tree, the bin-and-merge engine with buffered writes | Sequential append into memory, flushed later | Checks memory then sorted files with probabilistic filters | Good with leveled merging that keeps runs sorted | RocksDB, which is an embeddable high-write engine, Cassandra, which is a distributed wide-column store, and LevelDB, its lightweight predecessor |
A B+ tree, which is a balanced sorted tree where each node fills one disk page and leaves link for scans, stores only keys plus child pointers in internal nodes and key-to-row pointers in leaves. High fanout, which is hundreds of children per node, keeps depth at 3 to 4 levels even for billions of rows, so a point lookup costs at most that many page reads, and usually fewer because upper levels sit in the buffer pool, which is the memory cache for hot pages. Range scans find the starting leaf then walk the leaf chain, which is sequential disk access rather than random seeks.
Root [10 | 20]
/ | \
[1-9] [10-19] [20-...]
│ each node = one disk page (4KB/16KB)
│ internal nodes only store keys + child ptrs
│ leaves hold keys → row pointers and are linked (→) for range scans
Point lookup: 3 page reads (root→branch→leaf) even for 10M rows (fanout ~100)
Range scan 10..19: find leaf for 10, then walk leaf linked list (sequential I/O)An LSM tree, which is a log-structured merge tree that buffers writes in memory and merges sorted files later, avoids random writes entirely. Each edit appends to a write-ahead log for crash safety and inserts into a memtable, which is a sorted in-memory table typically tens of megabytes. When the memtable fills it flushes as one immutable sorted file called an SSTable. Reads check newest to oldest across memory then files, using bloom filters, which are small probabilistic structures answering definitely-absent or possibly-present per file, to skip files that cannot hold the key. Background compaction, which is merge-sorting files and dropping overwritten and deleted entries, bounds the file count.
Write path: PUT key=foo → WAL (seq log) → memtable (skiplist / RB-tree)
memtable full (64MB) → flush → SSTable [sorted, immutable]
Read path: GET foo → memtable → L0 SSTables (newest→oldest) → L1 … Ln
→ bloom filter per SSTable (skip if definitely not present)
→ block index → data block (4KB)
Compaction (leveled):
L0(10 files, overlapping) → merge sort → L1(1 file, non-overlapping)
Rewrites data, drops deletes, enforces sorted runs. Can stall writes if L0 piles up.Disk sees only sequential appends with no seeks, so ingestion sustains millions of writes per second on hardware where random rewrites would stall.
Each read may consult several files across levels. Filters plus block cache keep median latency low, but the tail grows with the number of levels.
One key can exist in many files until merging, so 20 to 50% transient extra space is normal and must be provisioned.
Durability and concurrency are different jobs. The write-ahead log handles durability by forcing each change to an append-only record before any page or memtable mutation, so a crash replays from the last checkpoint instead of finding half-written pages. Multi-version concurrency, which gives each write a new row version stamped with its transaction identifier while readers see a snapshot from their start time, handles concurrency by letting writers never block readers. The two combine to explain routine operations: dead versions accumulate and must be cleaned, and bulk loads can relax log syncing only when the input can be replayed.
Append each change to the log and flush it, optionally batching flushes across commits, before touching any page or memtable. On crash, replay from the last checkpoint restores acknowledged edits even when their pages never reached disk.
BEGIN; UPDATE accounts ... ; -- WAL record appended + fsync
-- even if B+ page not yet flushed, crash → replay recovers
COMMITEach write creates a new row version stamped with its transaction. Readers opening a snapshot see only versions visible at their start time, so long reports never block incoming edits.
The selection rule follows the dominant access pattern. Frequent range scans, secondary indexes, and modest write ratios favor sorted pages with predictable point reads, where the working set fits the buffer pool. Append-mostly floods such as time series and counters favor buffered merges, where median reads stay fast through filters and cache but the 99th percentile varies with merging backlog. Operations differ accordingly: one side tunes vacuuming and page fill, the other tunes merging threads and filter sizing.
| Signal | Sorted pages fit better | Buffered merges fit better |
|---|---|---|
| Access pattern | Many range scans, secondary indexes, low write ratio | Write-heavy, append-mostly, time-series and counters |
| Latency shape | Predictable point reads when the working set fits memory | Fast median with filters and cache, with merging-driven tail variance |
| Operations burden | Vacuum tuning and index bloat monitoring | Compaction tuning, filter sizing, and write throttling |
Count the operations before arguing. A sorted tree with 16 KB pages and roughly 200 keys per node holds 200 entries at one level, 40,000 at two levels, 8 million at three, and 1.6 billion at four, because each level multiplies by the fanout. A billion-row index is therefore four levels deep, so a point lookup costs at most four page reads, and usually one or two because the root and branches stay cached. A buffered merge flips the bill: a 1 KB write costs one sequential log append plus a memory insert measured in microseconds, but a cold point read may probe several files across levels, each gated by a filter with roughly 1% false positives. Sizing the filter near 10 bits per key spends a little memory to skip almost every useless probe.
| Operation | Sorted-page cost | Buffered-merge cost |
|---|---|---|
| Write one 1 KB row | Random page read plus rewrite, with amplification near 2 to 4 times including the log | Log append plus memory insert, with amplification near 10 to 30 times after repeated merging |
| Point read served from memory | One to two page reads, sub-millisecond | Memory hit or one file probe, sub-millisecond |
| Point read from cold disk | Three to four disk reads, near 10ms on flash | Up to one probe per level, with filters skipping most and a tail near 10 to 30ms |
Both failures look like the database got slow from the application, but the metrics diverge. On sorted pages, a hot table taking thousands of updates per second leaves a dead version per update, background cleaning falls behind, the table doubles in size while row counts stay flat, and scans that took seconds take minutes. The response is aggressive cleaning on hot tables, short transactions so dead rows become reclaimable, and monitoring of bloat rather than row counts. On buffered merges, writes arrive faster than merging, the youngest level accumulates dozens of overlapping files, every read checks all of them so the 99th percentile triples, then the engine deliberately stalls writes to let merging catch up and throughput falls off a cliff. The response is write rate limits, more merging threads, and memtable sizing matched to burst headroom.
Disk usage climbs while row counts stay flat, and sequential scans slow proportionally to the bloat factor. Tune background cleaning to be aggressive on hot tables, keep transactions short, and watch dead-version ratios and table age rather than row counts alone.
Write latency spikes arrive together with rising file counts and pending merge bytes at the youngest level. Rate-limit writes, raise merging parallelism, and size level triggers and memtables so bursts fit without stalling.
Sorted-page systems revolve around memory and garbage: size the shared buffer pool to the working set rather than the whole table, leave free space per page on update-heavy tables so edits land without splits, and raise cleaning workers and cost limits on hot tables while watching transaction age. Buffered-merge systems revolve around burst absorption and read gating: memtables near 32 to 128 MB absorb bursts while flushing promptly, leveled merging favors reads and tiered merging favors write throughput, filters near 10 bits per key gate useless probes with a cache sized for hot keys, and log syncing stays strict except for replayable bulk loads.
Engines decide how one machine stores bytes reliably, and multi-version rows already let readers snapshot without blocking writers. Snapshots raise the question the layout alone cannot answer: when two transactions interleave against the same rows, with one transferring money while another reads balances mid-transfer, which interleavings are legal and what does the report observe. That is the isolation contract.