Storage Architecture

How data lives on disk — pages, heap files, and the two dominant storage engine models

Why

Every database decision — index choice, write amplification, compression, compaction — traces back to how data is stored on disk. Disk I/O is the primary bottleneck in most database workloads. Understanding the storage layer explains why bulk inserts to a B-tree index are slow, why LSM-tree databases handle high write throughput better, and why sequential reads are orders of magnitude faster than random ones.

Intuition

Databases don't read individual bytes — they read and write in fixed-size pages (typically 8KB or 16KB). Even reading one row loads the entire page into the buffer pool. This is why sequential access (reading pages in order) is fast and random access (jumping between pages) is slow — the disk head has to seek for each one.

Two fundamental storage models dominate: B-tree (update in place — good for reads and mixed workloads) and LSM-tree (append-only — good for write-heavy workloads). PostgreSQL and MySQL use B-trees; Cassandra, RocksDB, and LevelDB use LSM-trees.

Explanation

Pages, heap files, and the buffer pool

Heap file: unsorted collection of pages containing rows └── Page 1: [row1][row2][row3][free space] └── Page 2: [row4][row5][...] └── Page N: ... Buffer pool: in-memory cache of recently accessed pages - Database checks buffer pool before going to disk - Dirty pages (modified but not yet written) are flushed periodically - Page eviction uses LRU or clock algorithm Row (tuple) layout within a page: - Fixed-length columns stored directly - Variable-length columns (TEXT, VARCHAR) stored inline up to a limit, then moved to a TOAST/overflow table with a pointer in the main page

The buffer pool hit rate is the single most important performance metric for a read-heavy database. A cold cache (restart, new query patterns) causes a surge of disk reads until pages are warmed up.

B-tree vs LSM-tree

B-tree (PostgreSQL, MySQL, SQLite)

Updates modify pages in place. Reads are fast — data is where you expect it. Writes cause random I/O — updating a row touches the page wherever it lives. Good for read-heavy and mixed workloads. Write amplification is low per operation but random.

LSM-tree (Cassandra, RocksDB)

Writes go to an in-memory buffer (memtable), then flush to immutable sorted files (SSTables) on disk. Reads must merge data across multiple SSTables. Excellent write throughput. Background compaction merges SSTables — trades read amplification for write speed.

Write-Ahead Log (WAL)

Every change is first written to the WAL (sequential log file) before modifying the actual data pages. On crash recovery: - WAL is replayed to re-apply any committed changes not yet in data files - Uncommitted transactions are rolled back Benefits: - Sequential WAL writes are fast (no random I/O) - Data pages can be written to disk lazily (batched) - WAL also serves as the replication stream — replicas replay the WAL

The WAL is also the foundation of point-in-time recovery — you can restore a database to any moment by replaying the WAL from a base backup up to that timestamp.

← Previous Next →