Storage Engines and Page Layout

A modern NVMe SSD delivers ~500K random 4 KB reads per second but can sustain >3 GB/s sequential throughput. HDDs are worse: a 7200-RPM disk costs ~5 ms of seek time per random access — 200 random reads per second vs 100+ MB/s sequential. That 1000x gap is why database engineers obsess over access patterns before algorithm complexity.

The core rule: minimize random I/O; maximize sequential I/O. Every structural choice — B-trees, LSM-trees, column storage, buffer pools — is downstream of this physics. A "fast" algorithm that causes random disk access will lose to a "slow" algorithm that reads sequentially.

Databases split storage into fixed-size pages (typically 4 KB, 8 KB, or 16 KB — matching or being a multiple of the OS page size). Every read and write is an integer number of pages. Benefits:

• Predictable addressing: byte_offset = page_id * page_size — no scanning to find page $n$.
• Buffer pool simplicity: the pool allocates uniform frames; no fragmentation bookkeeping.
• Atomic replacement: OS guarantees single-sector writes are atomic; databases extend this to a page with checksums and WAL.

Postgres defaults to 8 KB; SQLite to 4 KB; InnoDB to 16 KB. Going larger helps sequential scans; going smaller helps small random point lookups — there is no universally correct answer.

The simplest on-disk table layout is a heap file: an unordered collection of pages. Inside each page, a slotted page design handles variable-length rows without external fragmentation.

The slot array is stable — external indexes store (page_id, slot_id), not byte offsets. When a row is updated in place and needs more space, its data moves but the slot pointer is patched; indexes are unaffected. Deletion zeroes the slot; VACUUM reclaims space lazily.

Row stores serialize an entire row contiguously — ideal for OLTP where a query fetches one row (SELECT * WHERE id = 42). Column stores serialize a single column across all rows — ideal for OLAP aggregations that touch one column of millions of rows.

Column stores also enable vectorized execution: a tight loop over an array of int64s is SIMD-friendly in a way that a loop over heterogeneous row structs is not.

The buffer pool keeps recently-used pages in RAM, serving most reads with zero disk I/O. It is typically the single most important configuration knob (shared_buffers in Postgres, innodb_buffer_pool_size in MySQL — commonly 25% of RAM on a dedicated server).

Key mechanics:

• Page table: hash map from (file_id, page_id) to a buffer frame pointer — O(1) lookup.
• Eviction: most engines use LRU-K (tracks last K accesses) to avoid large sequential scans evicting hot OLTP pages.
• Dirty pages: modified in memory but not yet flushed. Before eviction, a dirty page must be written to disk — but only after WAL has recorded the change.
• Pinning: a page in active use is pinned; the eviction thread cannot steal it mid-query.

Flushing every dirty page on every commit would be agonizingly slow. WAL makes this fast and safe simultaneously with one rule: log the change before applying it to the page.

On commit, only the log records need to be fsynced; data pages can be flushed lazily by a background writer. On crash, the engine replays the log from the last checkpoint to reconstruct any page not yet written to disk.

-- Postgres: inspect recent WAL records
SELECT lsn, xid, resource_manager, record_length
FROM pg_walinspect(
  pg_current_wal_lsn() - '1MB'::pg_lsn,
  pg_current_wal_lsn()
);

WAL wins because it converts random data-page writes into sequential log appends — the fastest possible disk access pattern.

A transaction write touches the log before touching the page:

If the WAL grows forever, crash recovery replays forever. Checkpoints bound recovery time: flush all dirty buffer-pool pages to disk, write a checkpoint LSN to the WAL. On restart, REDO only replays records after the last checkpoint.

Postgres triggers a checkpoint every checkpoint_timeout seconds (default 5 min) or when max_wal_size is reached. The flush is spread over checkpoint_completion_target (default 0.9) of the interval to avoid I/O spikes.

Gotchas:

• Too-frequent checkpoints spike I/O and hurt write throughput.
• Too-infrequent checkpoints make crash recovery slow and let WAL files accumulate on disk.
• Watch pg_stat_bgwriter — if checkpoints_req (triggered by WAL size) exceeds checkpoints_timed, increase max_wal_size.

Read path (SELECT * FROM orders WHERE id = 99):

1. Hash (file, page_id) → check buffer pool. On hit, return immediately — no disk I/O.
2. On miss, pick a victim frame (evict dirty frame if needed), read page from disk, insert into pool, return.

Write path (UPDATE orders SET status = 'shipped' WHERE id = 99):

1. Generate WAL record with before/after-image.
2. Append to in-memory WAL buffer.
3. Apply change to buffered page (mark dirty).
4. On COMMIT: fsync WAL buffer. Caller gets confirmation. Done.
5. Background: dirty page eventually flushed by bgwriter or checkpoint.

The asymmetry is intentional: reads can tolerate stale pages from RAM; writes must serialize through the log first to guarantee durability.