Database Storage Primer

The planner for our SELECT * FROM users WHERE id = 42 has decided to use the primary-key index. The storage engine's job from here is mechanical: descend the index to find the heap page that holds row 42, read the page, decode the tuple, hand it back to the executor. To understand that, you have to understand pages and the buffer pool.

The page is the unit of everything

Database files are not random byte streams. They are arrays of fixed-size pages, picked to be a small multiple of the disk sector size and the filesystem block size:

• Postgres: 8 KB default (compile-time setting).
• MySQL InnoDB: 16 KB default (configurable 4 / 8 / 16 / 32 / 64 KB).
• SQL Server: 8 KB fixed.
• Oracle: 8 KB default, configurable 2–32 KB.
• SQLite: 4 KB default (configurable 512 B – 64 KB).

The page is the unit of everything: the unit of I/O (one page is read or written, not one row), the unit of the buffer pool (one entry caches one page), the unit of locking on many engines, the unit of WAL log records ("page X bytes 100–116 changed to ..."). Pick the wrong page size and the entire engine's performance shifts.

The slotted-page layout

Rows are variable-length but pages are fixed. The standard solution — used by Postgres, MySQL InnoDB, SQL Server, SQLite, basically everyone — is the slotted page:

+--------------------------------------------------------+ offset 0
| Page header                                            |   24 bytes
|   pd_lsn  (WAL position)                               |
|   pd_checksum                                          |
|   pd_lower (end of slot array)                         |
|   pd_upper (start of tuple data)                       |
|   pd_special, flags, etc.                              |
+--------------------------------------------------------+
| Slot 0  →  offset 7900 (16 bytes)                      |  slot
| Slot 1  →  offset 7820 (32 bytes)                      |  array
| Slot 2  →  offset 7760 (52 bytes)                      |  grows
| ...                                                    |  down ↓
+----------------+---------------------------------------+ pd_lower
|                                                        |
|        FREE SPACE  (pd_upper - pd_lower bytes)         |
|                                                        |
+----------------+---------------------------------------+ pd_upper
| ...                                                    |  tuple
| Tuple 2 (52 B): xmin xmax | id=42 | name='alice' |...  |  data
| Tuple 1 (32 B): xmin xmax | id=41 | name='bob'   |...  |  grows
| Tuple 0 (16 B): xmin xmax | id=40 | ...                |  up ↑
+--------------------------------------------------------+ offset 8191

The slot array grows down from the header; the tuple data grows up from the bottom; free space sits in the middle. To find row 42, the engine reads slot N (constant time, since slot entries are 4 bytes), finds offset 7900 and length 16, and decodes 16 bytes there. Inserts pack the new tuple at the top of the free region and add one slot. Deletes mark the slot dead — the space is reclaimed by VACUUM / compaction later.

Each tuple has its own per-row header: in Postgres, xmin(the transaction that inserted it) and xmax (the transaction that deleted it). MVCC visibility checks happen during decoding — that's how multiple versions of row 42 can coexist on the same page.

Big rows: TOAST and overflow pages

A tuple has to fit in one page. What about a 5 MB text column? Every engine has an overflow story:

• Postgres TOAST (The Oversized-Attribute Storage Technique): if a tuple exceeds ~2 KB, large attributes get compressed, then sliced into ~2 KB chunks stored in a sibling pg_toast_* table. The main tuple keeps a pointer. Transparent on read, painful on UPDATE of a TOASTed column (the whole new version is re-written).
• MySQL InnoDB: variable-length columns over a threshold are stored in overflow pages (one or many), with a 20-byte pointer left inline.

The buffer pool

Reading 8 KB from NVMe is ~100 μs. Reading 8 KB from RAM is ~50 ns. Three orders of magnitude. So every database keeps an in-memory cache of pages — the buffer pool — indexed by a hash table on (relation_oid, page_number):

Postgres:  shared_buffers   = 25% of RAM   (recommended starting point)
           effective_cache_size = ~50-75% of RAM (planner hint, not an allocation)
MySQL:     innodb_buffer_pool_size = 70-80% of RAM on a dedicated server
SQL Svr:   max server memory       = total RAM - (~4 GB for OS)
Oracle:    db_cache_size + sga_target / memory_target

Target buffer-pool hit ratio on OLTP: ≥ 99%.
A 95% hit ratio sounds high but means 1 in 20 reads goes to disk —
20× the latency of the cached path.

Postgres is the unusual one: it deliberately keeps shared_buffers small and relies on the OS page cache for the rest, because Postgres pages live in regular files and the OS will cache them anyway. MySQL InnoDB does the opposite — uses O_DIRECT and a huge buffer pool so the OS page cache is not a second copy.

Page replacement and pin counts

The buffer pool is finite, so something has to be evicted when a new page comes in:

• Postgres: clock sweep. Each buffer has a usage counter (0–5); a rotating "clock hand" decrements counters as it passes and evicts the first buffer at zero. Cheap, approximates LRU.
• MySQL InnoDB: an LRU variant with midpoint insertion — newly read pages enter at the midpoint of the LRU list, not the head. A large sequential scan can't pollute the "hot" half of the cache by flushing out frequently-used pages.
• Pages currently in use are pinned — a refcount that prevents eviction while a query is reading the page or a background writer is flushing it.

Dirty pages, checkpoints, background writers

When an UPDATE modifies a page, it's marked dirtyin the buffer pool. Writing every dirty page back to disk on every commit would be brutal; instead:

1. The change is logged to the WAL (covered in Section 04). This is what makes the commit durable.
2. The dirty page itself sits in the buffer pool, written back lazily by a background writer at a steady rate, or in a big batch at a checkpoint.
3. A checkpoint flushes all currently-dirty pages so the WAL before the checkpoint can be reclaimed. Triggers: every checkpoint_timeout (default 5 min in Postgres) or when the WAL fills max_wal_size.

A badly-tuned checkpoint stalls writes for seconds while the kernel flushes gigabytes of dirty pages through fsync — a classic Postgres production incident. Postgres's checkpoint_completion_target(default 0.9) spreads the write out across most of the interval to smooth the spike.

Structure: wide, shallow, fully sorted

A B+tree is a balanced n-ary tree where:

• Internal nodes hold separator keys and pointers to children. They route traversals — they never hold row data.
• Leaf nodes hold either the row itself (clustered index, e.g. MySQL InnoDB primary key) or a pointer to the row in the heap (non-clustered, e.g. Postgres).
• Leaves are linked in a doubly-linked list in key order. This is the plus in B+tree, and it's what makes WHERE id BETWEEN 40 AND 50 cheap.

The branching factor is huge: a 16 KB page minus headers, divided by (key size + pointer size). For a 16-byte separator key plus an 8-byte child pointer in a 16 KB page, the fan-out is roughly ~600. With that fan-out:

fanout = 600

depth   max rows
  1       600              (root + 600 leaves)
  2       360,000
  3       216,000,000
  4       129,600,000,000  (130 billion)

A B+tree with 4 levels covers a billion-row table.
Postgres logs index depth at CREATE INDEX VERBOSE / EXPLAIN.
You will basically never see depth > 5 in production.

Traversal — what SELECT id = 42 actually does

1. Look up the index's root page (always known — stored in system catalog, pinned in buffer pool).
2. Binary-search the root's separator keys for 42. Follow the pointer to the next-level child.
3. Repeat for each internal level. Each step is a page lookup — almost always a cache hit, ~150 ns.
4. Reach a leaf. Binary-search again, find the entry for key 42. Clustered index: the row is right there. Heap-organised (Postgres): the leaf holds a (page, slot) tuple ID; fetch that heap page, decode tuple.

For a depth-4 tree with everything cached: 4 page reads ≈ 600 ns. With one disk miss to the heap on NVMe: ≈ 200 μs. With a totally cold cache: ≈ 1 ms. The fact that these three are predictable is why B+trees won.

Range scans — the doubly-linked leaves

SELECT * FROM users WHERE id BETWEEN 40 AND 50: descend once to find 40, then walk the leaf linked list right until a key exceeds 50. No re-descent per row. This is why B+trees beat hash indexes on range queries — and why WHERE created_at > ...on a B+tree index turns into a sequential scan of a few leaves.

Splits and merges

When an insert targets a full leaf, the engine splits it: allocate a new page, move half the entries to it, push a new separator key up to the parent. If the parent is also full, it splits too — the cascade can theoretically reach the root and grow the tree by one level. Symmetrically, deletes can underflow a leaf and merge it with a sibling (some engines, like Postgres, are lazy here and let pages stay half-empty until VACUUM).

Splits are expensive: they rewrite two pages, modify a third (parent), and emit WAL records for all of them. A bulk-insert workload into a randomly-ordered key gets a steady stream of splits; sequential inserts hit the rightmost leaf and split it once before moving on (much cheaper). This is why monotonically increasing primary keys (timestamps, BIGSERIAL) are much kinder to a B+tree than random UUIDs — UUIDs scatter inserts across every leaf and trash the buffer pool.

Concurrency: lock coupling and B-link trees

Multiple queries traverse the tree simultaneously; one might be splitting while another reads. Naïve locking — take a write latch on every node from root to leaf — would serialize the whole tree on every modification. Real engines use:

• Lock coupling / latch crabbing: take a latch on the parent, then the child, then release the parent. Readers do this with shared latches; writers with exclusive latches. Concurrent reads don't block each other; only the path actively being split is locked.
• B-link trees (Lehman & Yao, 1981; used by Postgres's nbtree): each internal node has an extra right-link pointer. A reader that arrives at a node mid-split can follow the right-link to find the missing key instead of restarting from the root. This removes the need to hold parent latches during splits — splits become more concurrent-friendly.

When the planner picks something else

B+tree is not the only index option:

• Hash: O(1) lookup but no range, no ordering. Postgres ships hash indexes; rarely the right pick because B+tree point lookups are already O(log n) with n=4 in practice.
• GIN (Generalized Inverted Index): for arrays, JSONB, full-text. Inverted: maps each token to a list of row IDs.
• GiST / SP-GiST: framework for geometric / range / custom indexes (PostGIS, exclusion constraints).
• BRIN (Block Range INdex): tiny index for huge, sorted tables (time-series, append-only). Stores just min/max per block range — orders of magnitude smaller than a B+tree, useful when the planner only needs to skip blocks.
• LSM: not pure index, more of a storage layout — covered in Section 03.

Origins: O'Neil et al, 1996 ("The Log-Structured Merge-Tree"). Made famous and re-shaped by Google's Bigtable (2006), LevelDB (open-source 2011), then RocksDB (Facebook fork of LevelDB, 2012). Today LSM is the storage layout under RocksDB, Cassandra, ScyllaDB, HBase, InfluxDB, CockroachDB (which runs on Pebble, an LSM rewrite), and most modern KV stores.

The basic shape

            ┌─────────────────────────┐
write ───►  │  WAL  (sequential file) │   durability
            └─────────────────────────┘
            ┌─────────────────────────┐
            │  Memtable (skiplist)    │   recent writes, in RAM
            │  ~64 MB                 │   sorted by key
            └────────────┬────────────┘
                         │ when full → flush
                         ▼
            ┌─────────────────────────┐
            │  L0:  SSTable SSTable … │   recent flushes (overlap)
            ├─────────────────────────┤
            │  L1:  SSTable           │   ~10× L0 size, no overlap
            ├─────────────────────────┤
            │  L2:  SSTable           │   ~10× L1
            ├─────────────────────────┤
            │  L3:  SSTable           │   ~10× L2
            ├─────────────────────────┤
            │  ...                    │
            └─────────────────────────┘

Writes always flow top → bottom. Reads check every layer until they find the key (or run out). All on-disk layers are immutable — once written, an SSTable file is never modified. Changes happen only by writing newer files and eventually compacting them.

The write path — pure sequential

1. Append a record to the WAL (sequential disk write).
2. Insert into the in-RAM memtable (skiplist or red-black tree, both O(log n)).
3. Return. The write is durable (WAL) and visible (memtable).

No B+tree descent, no page split, no random write. On NVMe with group commit, this is ~10–50 μs per write — and the throughput ceiling is the sequential write speed of your device, not the random-write speed. That's why LSMs land on benchmarks north of 100K writes/sec/core where B+trees plateau much earlier on the same hardware.

Memtable flush → SSTable

When the memtable hits its size limit (default 64 MB in RocksDB), it's frozen and a background thread writes it out as an immutable, sorted SSTable (Sorted String Table) file in L0. A new empty memtable takes over. The SSTable file format is roughly:

SSTable file layout
┌──────────────────────────────────┐
│ Data blocks (~4 KB each)         │   key/value pairs, sorted
│   block 0: keys aaa…abc          │
│   block 1: keys abc…ade          │
│   …                              │
├──────────────────────────────────┤
│ Index block                      │   one entry per data block
│   (last key, block offset)       │
├──────────────────────────────────┤
│ Bloom filter (~10 bits/key)      │   "key probably / definitely not"
├──────────────────────────────────┤
│ Footer (offsets, magic, version) │
└──────────────────────────────────┘

Bloom filters are crucial: each SSTable has one, sized so the false-positive rate is ~1%. A point lookup for key K consults the bloom filter first — a few hashes, no disk I/O — and skips the entire SSTable if the answer is "definitely not in this file." Without bloom filters, every read would touch every SSTable.

Compaction — the bill comes due

SSTables accumulate. Without cleanup: every read would touch hundreds; deleted keys would never go away (deletes in LSM are actually tombstones — a record saying "this key is now gone"). Compaction is the background process that merges SSTables together, dropping overwritten and tombstoned entries:

• Size-tiered compaction (Cassandra default, historically): when L0 has N tables of similar size, merge them all into one larger table. Simple, but read amplification can be high during transient bursts.
• Leveled compaction (LevelDB / RocksDB default): each level is ~10× larger than the previous; within a level (except L0), key ranges don't overlap. Merge L_i into L_(i+1) one chunk at a time. Lower read amp (≤1 SSTable per level beyond L0), higher write amp.
• Universal compaction, FIFO compaction: tuned variants. RocksDB exposes both.

The three amplifications

LSM performance is described by three numbers, and they trade off:

Read amplification   = pages read per logical read
                       (LSM leveled: ~ L + 1)
                       (B-tree:      ~ depth, ≤ 4-5)

Write amplification  = bytes written to disk per byte of user write
                       (LSM leveled: typically 10-30×)
                       (LSM tiered:  typically 5-15×)
                       (B-tree:      typically 1-2×)

Space amplification  = on-disk size / logical data size
                       (LSM leveled: ~ 1.1×)
                       (LSM tiered:  ~ 2×)
                       (B-tree:      ~ 1.3-2×, fragmentation)

You can't minimize all three at once. Leveled compaction minimizes space and read amp at the cost of write amp; tiered minimizes write amp at the cost of space and read amp; choose by workload. RocksDB's tunables (level0_file_num_compaction_trigger, max_bytes_for_level_multiplier, compaction_pri, rate_limiter_bytes_per_sec) are all knobs that move the three numbers around.

Read path — and why it can stall

1. Check the memtable (in-RAM, microseconds).
2. Check each L0 SSTable (they may overlap). Bloom filter first; if positive, read the SSTable index, then the data block.
3. For each lower level: bloom-filter check the one SSTable whose key range covers the lookup; if positive, read the index, then the data block.
4. If you find the latest version (or tombstone), return.

Worst case: bloom-filter false positive at every level → read amp = number of levels. A common production failure mode: the compaction queue grows faster than compactors can drain it, L0 accumulates dozens of SSTables, point lookups now check 30+ files instead of 4–5. Latency spikes — but throughput on writes still looks healthy. The classic LSM debug story.

When to reach for which

• B+tree: relational OLTP with mixed read/write, frequent point + range queries, low write amp tolerance. Postgres, MySQL — your transactional system of record.
• LSM: write-heavy ingestion (metrics, events, logs), key-value lookups with bloom filters, tolerant of compaction CPU. RocksDB-as-embedded-storage, Cassandra/Scylla for time-series, ClickHouse for analytics.
• Both: increasingly, hybrid designs. Postgres has zheap, MySQL has experimented with LSM column stores, CockroachDB chose LSM (Pebble) because their workload is write-heavy distributed. The choice is per-table or per-engine, not per-language.

The rule, in one line

Write-ahead logging (WAL) means: before any modification to a data page is allowed to reach durable storage, a log record describing that modification must already be on durable storage. The page modification can flush late, never, or out of order — the WAL is the canonical truth.

Why this rule and not the simpler "write the page directly"? Because pages are large (8–16 KB), random across the disk, and modifications come in tiny patches (16 bytes here, 4 bytes there). A WAL append is sequential, batched across many transactions, and sized to whatever the changes were. One fsync on the WAL commits thousands of patches; one fsync per dirty page would crush you.

A commit, step by step

For the UPDATE form of our request (UPDATE users SET email = ... WHERE id = 42), what actually happens betweenCOMMIT and the response going back:

1. The executor locates and modifies the heap page in the buffer pool. The page is now dirty in RAM. Nothing on disk has changed.
2. A WAL record is appended in memory describing the change:page X, slot S, set bytes 32-79 = .... Each record carries the page LSN (Log Sequence Number) it modifies.
3. On COMMIT, a commit record is appended. The WAL writer flushes the in-memory WAL buffer to disk (via write()) and calls fsync() on the WAL file. Only when fsync returns does COMMIT return success.
4. The dirty data page sits in the buffer pool. It gets flushed minutes later by the background writer or at the next checkpoint. By the WAL rule, this is safe: if we crash, the WAL replay will recreate the modification.

The fsync on the WAL is the durability bottleneck. NVMe with a battery-backed cache: ~50–500 μs. Consumer NVMe with no power-loss protection: 5–15 ms. Spinning disk: 5–50 ms. Two fsyncs per commit (Postgres also fsyncs the data file at checkpoint) on a slow disk will pin your max commit rate to maybe 100 TPS per connection.

Crash recovery: ARIES in three letters

Mohan et al, 1992 (the ARIES paper) defined the recovery algorithm that every modern relational DB implements some flavor of. Three phases, run on the WAL:

• Analysis. Scan forward from the last checkpoint. Determine which transactions were in flight at crash time (active transactions list) and which pages were dirty (dirty page table).
• Redo. Replay every WAL record from the dirty page table's minimum LSN forward, regardless of whether the original transaction committed. This brings every page up to its last logged state — the database is now exactly where it was at crash time, except all changes are now actually on disk.
• Undo. For every in-flight (uncommitted) transaction at crash time, walk backward through its WAL records and apply the inverse. After undo, only committed transactions remain visible.

Recovery time scales with the WAL between checkpoints, not with database size. This is why checkpoints exist and why you tunemax_wal_size / innodb_log_file_size — they bound how long recovery takes.

Group commit — fighting the fsync cliff

Every commit needs an fsync. With 1000 connections each committing at 200 TPS, that's 200K fsyncs/sec — impossible. The fix is group commit: hold a commit briefly, let any other commits queued up in the next few microseconds piggyback on the same fsync. One fsync, many commits. Throughput scales sharply with no change in semantics (each commit still waits for its data to be durable).

Postgres knobs: commit_delay (microseconds to wait before fsync, default 0) and commit_siblings(minimum other active transactions before delay kicks in, default 5). MySQL InnoDB: innodb_flush_log_at_timeout when flush mode allows batching.

The durability knobs you can actually tune

POSTGRES — synchronous_commit
  on            (default) fsync the WAL on every commit. ACID-safe.
                Cost: one fsync per commit (5-15 ms NVMe).
  local         fsync locally, but don't wait for sync replicas.
                Use when replica latency matters more than durability margin.
  remote_write  wait for replica to write WAL (no fsync) — survives
                primary failure but not simultaneous primary+replica crash.
  remote_apply  wait for replica to redo the WAL — strongest, slowest.
  off           batch up to wal_writer_delay (default 200 ms).
                You CAN lose up to ~600 ms of committed transactions
                on a crash. Never use in production unless you understand
                exactly what data is OK to lose.

MYSQL InnoDB — innodb_flush_log_at_trx_commit
  1   (default) write + fsync log on every commit. ACID-compliant.
  2             write log on every commit, fsync once per second.
                Survives MySQL crash, NOT OS / hardware crash within ~1 s.
  0             write + fsync once per second.
                Up to ~1 s of committed transactions lost on crash.

EVERY ENGINE — disk write cache
  Drive write caches that lie about completion (cheap consumer SSDs)
  break durability invisibly. Test with diskchecker.pl / fio with
  fsync verification, or use enterprise drives with power-loss protection.

Replication and CDC ride the WAL

The WAL isn't just for recovery. It's the canonical stream of database state changes, so it's the natural feed for:

• Physical replication: stream raw WAL records to a standby; the standby applies them byte-for-byte. Same major version required. Postgres streaming replication, MySQL binlog + position-based replica. Fast, but the standby is a perfect clone — no per-table filtering.
• Logical replication: decode WAL records into row-level events (INSERT id=42 with values {..}) and ship them. Per-table, version-flexible, can cross major versions. Postgres logical replication, MySQL row-based binlog. Slightly more CPU on the publisher.
• CDC / Change Data Capture tools: Debezium, Maxwell, Postgres's logical decoding plugins. They read the WAL and emit Kafka / Kinesis events. This is how every "event-driven" architecture downstream of an OLTP database actually works.
• Point-in-time recovery: take a base backup, archive every WAL segment thereafter, then replay WAL up to a chosen LSN or timestamp. The granularity is one WAL record — effectively per-transaction.

The WAL is, in effect, the database's public API for change. Once you internalize that, "the WAL is a stream of mutations and the table is its accumulator" — the LSM and stream-table duality both make more sense.

Red flags in code review

• synchronous_commit = off / innodb_flush_log_at_trx_commit = 2 in production for "performance." You've traded ACID durability for ~10% throughput. Group commit gets you most of that back with no durability loss. If you genuinely don't care about losing the last second of writes (analytics ingest, best-effort logs), say so explicitly — don't hide the trade in a config file.
• shared_buffers set to total RAM (or 90%+, on Postgres). Leaves nothing for the OS page cache, work_mem for query sorts, connection memory, or other processes. Postgres's 25% rule is the starting point; MySQL InnoDB's 70–80% applies because InnoDB uses O_DIRECT and skips the OS page cache.
• LSM compaction queue growing unbounded. Writes look fine; reads degrade silently as L0 fills with dozens of SSTables and every point lookup checks them all. Monitornum-files-at-level0 (RocksDB), set alerts, and throttle ingest before compaction collapses.
• B+tree index on a low-cardinality column (boolean, deleted_at, status_id with 4 distinct values). The index ends up larger than the table scan it's "helping," and the planner ignores it. Use a partial index (WHERE status = 'active') or no index and let the seq scan win.
• Hot row updated thousands of times per second. Counter rows, session-token rows, "last seen" timestamps. Every update generates a WAL record and dirties the same page; the WAL becomes the bottleneck and lock contention strangles you. Move it to a counter table with per-partition rows summed at read time, or to Redis with periodic flushes back.