How Databases Actually Store Data: Pages, Indexes, and WAL

From SQL to Durable Bytes

SQL makes storage look abstract. You insert a row, commit a transaction, and later select it by an indexed column. Underneath, the database is coordinating memory, pages, indexes, locks, logs, checksums, and operating-system I/O.

This article follows one useful path:

SQL statement -> query plan -> pages in buffer pool
             -> row and index changes -> WAL record
             -> durable commit -> later checkpoint

Understanding this path helps explain why a query can be fast once and slow later, why an index speeds reads but slows writes, and why a committed transaction can survive a process crash.

Pages Are the Storage Unit

Applications think in rows. Storage engines usually read and write fixed-size pages, commonly 4 KiB to 16 KiB. A page can contain a header, an array of row offsets, records, free space, and visibility information.

An offset table lets a row move within the page without changing references to the row’s slot. Variable-length fields such as text and JSON need this indirection. A database may also use a stable row identifier that points to a page and slot rather than embedding a byte offset that would become invalid after compaction.

page header
slot directory: [row 3 offset, row 2 offset, row 1 offset]
free space
row data growing from the end of the page

Pages are a practical compromise. Larger pages reduce bookkeeping and make sequential scans efficient, while smaller pages reduce the amount of unrelated data read for a point lookup. The best size depends on the storage engine, workload, and hardware.

Heap Storage and Row Layout

A heap table stores records without keeping them physically sorted by a primary key. Inserts can use available free space, and updates may create a new version when the new row no longer fits in its page.

Typical row-layout decisions include:

• Fixed-width columns are cheap to locate but can waste space.
• Variable-width columns need offsets and length metadata.
• Null bitmaps avoid storing a full value for absent fields.
• Alignment can make numeric reads faster at the cost of padding.
• Large values may be stored out of line with a pointer in the row.

A table scan is therefore a scan of pages, not a loop over a perfect in-memory array. Fragmentation, dead versions, and poor physical locality can make a scan much more expensive than the row count suggests.

B-Trees and the Cost of an Index

An index maps a key to a row location or primary-key value. A B-tree keeps keys ordered and stores many child pointers in each page. Its high fanout keeps the tree shallow, so a lookup typically touches only a few pages.

                 root page
              /      |      \
       internal   internal   internal
          / \        / \        / \
       leaf       leaf       leaf
          |         |          |
       row IDs    row IDs    row IDs

A composite index is ordered lexicographically. An index on (tenant_id, created_at) can efficiently find one tenant’s recent rows, but it may not help a query filtering only on created_at. Column order is a workload decision.

Indexes can also be covering. If a query needs only columns already stored in the index, the engine may avoid visiting the table page. This reduces random I/O, but the index becomes larger and more expensive to maintain.

Every write has a bill: update the table page, update affected indexes, generate log records, and possibly split a full index page. Index only real access patterns and verify with query plans.

B-tree page splits are one reason monotonically increasing keys behave differently from random keys. Sequential IDs mostly append to the right edge of the tree, which is cache-friendly but can create a hot page under extreme write concurrency. Random IDs distribute writes but cause more page churn and poorer locality. Neither is universally better; the workload decides.

The Buffer Pool

The buffer pool is the database’s managed cache of pages. A query asks for a page; if it is present, the engine uses the memory copy. Otherwise, it reads the page from storage and may evict another page.

Pages have states such as clean, dirty, pinned, or being flushed. A pinned page cannot be evicted while an operation is using it. A dirty page contains changes that have not yet been written to the data file.

This explains several common observations:

• A query is fast after a warm-up because its pages are cached.
• A large report can evict hot application pages and hurt unrelated traffic.
• More memory helps only when the working set benefits from caching.
• Sequential scans may need special policies so they do not pollute the cache.

Look at cache hit ratios together with latency. A high hit ratio does not prove the workload is healthy if the remaining misses are on a critical path.

Write-Ahead Logging

Data pages are written lazily. If the process crashes after modifying a page in memory but before flushing it, the database needs a durable record of the intended change. Write-ahead logging, or WAL, provides that record.

The rule is simple: the log record describing a page change must reach durable storage before the changed page is allowed to reach durable storage.

change page in memory
        |
append WAL record with page identity and log sequence number
        |
flush WAL when the transaction commits
        |
write dirty data page during a checkpoint

The log is sequential, which is generally cheaper than forcing many random data-page writes at commit time. A log sequence number lets recovery compare a page’s last applied log record with the log and avoid applying the same change twice.

Checkpoints and Crash Recovery

Recovery usually has a redo phase that reapplies durable changes not present in data pages, followed by an undo or transaction-cleanup phase for work that was not committed. Exact algorithms differ, but the goal is the same: restore a state that honors the durability and atomicity contract.

A checkpoint writes enough dirty pages and metadata to shorten future recovery. Checkpointing too aggressively creates write pressure; checkpointing too rarely makes crash recovery longer. Monitor checkpoint duration, WAL growth, flush latency, and recovery time rather than treating them as invisible internals.

MVCC: Why Readers Can See Different Versions

Many databases use multi-version concurrency control. An update creates a new visible version while older transactions may continue seeing the previous version. Readers do not always block writers, but old versions must eventually be cleaned up after no active transaction can see them.

Long-running transactions are dangerous because they keep old versions alive. They can increase table bloat, delay cleanup, and make vacuum or compaction work harder. Keep transactions short and avoid holding a transaction open while waiting on user input or a remote API.

Isolation levels choose which versions and concurrent changes a transaction may observe. Stronger isolation can prevent anomalies but may increase conflicts or coordination. Choose it based on the invariant you need, not because “serializable” sounds safer in every situation.

MVCC explains why count(*) and storage size can feel surprising. A table may contain dead versions that are invisible to new transactions but still occupy pages until cleanup. Heavy update workloads can therefore need vacuuming, compaction, fill-factor tuning, or partitioning even when the logical row count looks small.

What Performance Counters Mean

Useful counters become more meaningful when tied to internals:

Practical Performance Investigation

When a query is slow, inspect more than the SQL text:

1. Read the query plan and compare estimated versus actual row counts.
2. Check whether the access path is a sequential scan, index scan, or lookup.
3. Measure pages read from storage versus served from cache.
4. Look for sorting, hashing, spills, locks, and rows filtered after retrieval.
5. Check index bloat, table fragmentation, and stale statistics.
6. Measure p95 and p99 latency, not only the average.

An index may be ignored because the predicate matches too many rows, the statistics are stale, or the cost of random page reads exceeds a sequential scan. Adding an index without checking the plan can increase write cost while changing nothing.

Design Lessons for Application Developers

• Keep rows and indexes small enough to fit useful working sets in memory.
• Use stable, selective predicates and match composite-index order to queries.
• Avoid unbounded transactions and unnecessary index duplication.
• Batch writes when possible, but preserve clear transaction boundaries.
• Measure storage latency and WAL pressure during realistic load.
• Test restore and recovery, not only successful requests.

Databases are not magical tables. They are carefully engineered state machines moving pages between memory and durable storage while preserving correctness under concurrency and failure. Once that model is familiar, database behavior becomes something you can predict, measure, and improve.