Page Structure

Every piece of data you've ever stored in a database—every row, every column, every index entry—ultimately lives on a page. The page is the fundamental unit of I/O in virtually all database management systems, serving as the atomic container that bridges the gap between persistent storage and in-memory data manipulation.

Understanding page structure isn't merely academic detail; it's the foundation upon which all higher-level database operations are built. Query performance, storage efficiency, concurrency control, and recovery mechanisms all depend intimately on how pages are organized. A Principal Engineer working on database internals or optimizing storage-intensive applications must understand these concepts at a deep, intuitive level.

Before diving into page structure, we must understand why databases use pages in the first place. This isn't an arbitrary design choice—it's a carefully considered solution to fundamental constraints imposed by hardware and operating systems.

The Disk I/O Reality

Magnetic disks and even modern SSDs don't read or write individual bytes. They operate in fixed-size blocks, typically 512 bytes or 4KB for disk sectors and larger blocks for SSD pages. Any read or write operation, no matter how small the actual data, transfers an entire block.

Consider what happens without page abstraction:

• Read 1 byte? Transfer 4KB from disk
• Write 1 byte? Read 4KB, modify 1 byte, write 4KB back
• N random single-byte accesses? N × 4KB transfers

This mismatch between byte-addressable needs and block-addressable reality drove the invention of the page as a management abstraction.

The Buffer Pool Connection

Pages serve as the unit of transfer between disk and the buffer pool (main memory cache). When the database needs to access a row, it:

1. Determines which page contains the row (via page ID)
2. Checks if that page is in the buffer pool
3. If not, reads the entire page from disk into a buffer frame
4. Accesses the row within the in-memory page
5. Eventually, if the page was modified, writes the entire page back to disk

This page-at-a-time model has profound implications:

• Multiple rows on the same page share the I/O cost
• Rows physically near each other (on the same page) have temporal locality benefits
• Page size directly affects buffer pool hit rates and memory utilization

A database page is a carefully organized data structure, typically fixed at 4KB, 8KB, or 16KB. While implementations vary across database systems, the fundamental components remain consistent:

The Three-Region Model

Most database pages follow a conceptual model with three primary regions:

Why This Layout?

The bidirectional growth pattern (slots growing down, records growing up) is intentional:

1. Maximizes contiguous free space — All unused bytes form a single block, simplifying allocation
2. Eliminates internal fragmentation during initial insertions — New records and their slot entries simply claim space from opposite ends
3. Enables efficient compaction — When free space becomes fragmented, records can be compacted toward the bottom without invalidating slot numbers
4. Supports variable-length records — Unlike fixed-offset schemes, records of any size can coexist on the same page

The page header is the control structure that makes everything else on the page interpretable. Without the header, the remaining bytes would be meaningless. Let's examine each component in detail:

The LSN: Cornerstone of Recovery

The Page LSN (Log Sequence Number) deserves special attention. This 8-byte field records the LSN of the most recent WAL (Write-Ahead Log) record that modified this page. During crash recovery:

1. Recovery scans the WAL from the checkpoint
2. For each WAL record, it reads the target page
3. It compares the WAL record's LSN to the page's LSN
4. If WAL LSN > Page LSN, the modification is replayed (redo)
5. If WAL LSN ≤ Page LSN, the page already has this change (skip)

This mechanism ensures idempotent redo—replaying the same WAL record multiple times yields the same result. The Page LSN makes this possible by indicating the page's current state in the modification timeline.

Lower and Upper Pointers: The Free Space Boundaries

These two offsets define the free space region:

┌─────────────────────────────────────────────────────────┐
│ Header │ Slot Dir...          │ FREE SPACE │ Records... │
│  (24B) │                      │            │            │
└────────┴──────────────────────┴────────────┴────────────┘
         ↑                      ↑            ↑
         0                   LOWER        UPPER          8191
                            (100)         (7800)
         │────── allocated ─────│── free ───│── allocated ──│

• Lower points to the first byte after the slot directory
• Upper points to the first byte of the record region
• Free Space = Upper - Lower bytes

When inserting a record:

1. Check if (record size + slot entry size) ≤ (Upper - Lower)
2. If yes: copy record starting at Upper, decrement Upper by record size
3. Add slot entry at Lower, increment Lower by slot entry size

Not all pages are created equal. Databases use different page types for different purposes, each with specialized structures optimized for their role:

Heap Pages vs. Index Pages

The distinction between heap (data) pages and index pages is fundamental:

Heap Pages:

• Store actual row data with all column values
• Records are not necessarily sorted
• Support in-place updates (with MVCC caveats)
• Primary concern: space utilization, hot updates

Index Pages:

• Store keys and pointers (either to heap or to other index pages)
• Entries are sorted by key value
• Leaf pages linked for range scans
• Primary concern: fanout, balance, split/merge overhead

Both page types share the basic header + slot directory + record structure, but their internal record formats and management algorithms differ significantly.

Choosing the right page size is one of the most consequential decisions in database design. While most systems provide sensible defaults, understanding the tradeoffs enables informed tuning for specific workloads.

Workload-Specific Recommendations

Modern SSD Considerations

SSDs have changed some traditional assumptions:

• SSD internal page size is typically 4KB-16KB
• Write amplification occurs when database page size doesn't align with SSD page size
• NVMe SSDs can handle smaller random I/Os efficiently, reducing the penalty for smaller pages
• Some databases (e.g., RocksDB, TiKV) use variable-size blocks rather than fixed pages

Managing free space within a page is a microcosm of the broader memory management problem. The database must track available space, allocate from it efficiently, and reclaim space from deleted or updated records.

States of Space on a Page

Space on a database page exists in several states:

1. Allocated (Live) — Currently used by live records
2. Allocated (Dead) — Used by deleted/obsolete records awaiting cleanup
3. Free (Contiguous) — Between slot directory and record region
4. Free (Fragmented) — Holes within the record region from deletions

The Fragmentation Problem

Consider a page with three 1000-byte records, then the middle one is deleted:

 Before deletion:               After deletion:
 ┌───────────────────┐           ┌───────────────────┐
 │ Header + Slots    │           │ Header + Slots    │
 ├───────────────────┤           ├───────────────────┤
 │ Free:  5000 bytes │           │ Free:  5000 bytes │
 ├───────────────────┤           ├───────────────────┤
 │ Record C (1000B)  │           │ Record C (1000B)  │
 │ Record B (1000B)  │           │ ████ HOLE 1000B ██│
 │ Record A (1000B)  │           │ Record A (1000B)  │
 └───────────────────┘           └───────────────────┘

After deletion:

• Contiguous free space: 5000 bytes
• Total free space: 6000 bytes (including the 1000-byte hole)
• Usable for a 5500-byte record? No! The hole fragments the space.

Every database operation ultimately translates to a sequence of page-level operations. Understanding these primitives reveals why certain operations are expensive and how the database maintains consistency.

The Insert Path in Detail

INSERT INTO orders (id, customer, amount) VALUES (42, 'Alice', 100.00);

┌──────────────────────────────────────────────────────┐
│ 1. Executor requests: insert this tuple on table heap │
└──────────────────────────────────────────────────────┘
                          │
                          ▼
┌──────────────────────────────────────────────────────┐
│ 2. Buffer manager: find page with sufficient space   │
│    - Consult Free Space Map (FSM)                    │
│    - FSM says page 47 has ~2KB free                  │
│    - Request page 47 into buffer pool                │
└──────────────────────────────────────────────────────┘
                          │
                          ▼
┌──────────────────────────────────────────────────────┐
│ 3. Lock page 47 (exclusive or content lock)          │
│ 4. Verify free space: Upper - Lower ≥ tuple + slot   │
│ 5. Generate WAL record (before modifying page)       │
│ 6. Write tuple at offset = Upper - tupleSize         │
│ 7. Add slot entry: slots[nslots++] = new offset      │
│ 8. Update header: Upper -= tupleSize, Lower += 4     │
│ 9. Mark page dirty in buffer pool                    │
│ 10. Release page lock                                │
└──────────────────────────────────────────────────────┘

Note how the page insert involves multiple subsystems: executor, buffer manager, lock manager, WAL writer, and the page manipulation itself. Each step is carefully ordered to ensure recoverability and concurrency safety.