Pages, Blocks, and Heap Files: How Database Storage Engines Layout Data on Disk

Suppose you are investigating a database server host.

You inspect a table containing 1,000,000 customer profile rows. On disk, that table is stored inside a file named users.ibd.

If you open that file in a hex editor, you don’t see raw SQL statements or CSV text lines.

Instead, you see a structured binary sequence divided into fixed-size chunks called Pages (or Blocks).

How does a database engine organize variable-length string fields ("Alex", "[email protected]") inside rigid disk files without wasting space or fragmenting storage when rows get updated?

The answer lies in the Slotted Page Architecture.

The Fundamental Storage Unit: The Page

Operating systems read and write to physical disk hardware in block units (typically 4KB sector blocks).

To align with OS disk I/O efficiently, database storage engines organize all disk data into fixed-size Pages:

MySQL InnoDB: Default page size is 16KB (16,384 bytes).
PostgreSQL: Default page size is 8KB (8,192 bytes).

Every table, index, and transaction undo log in a database is built from an ordered sequence of these fixed-size pages.

DATA FILE ON DISK (e.g. users.ibd)
+----------------+----------------+----------------+----------------+
| Page 0 (16KB)  | Page 1 (16KB)  | Page 2 (16KB)  | Page 3 (16KB)  | ...
+----------------+----------------+----------------+----------------+

When a database reads or writes a single row, it fetches or flushes the entire 16KB Page containing that row to or from RAM.

The Slotted Page Layout Architecture

How do you store variable-length rows inside a fixed 16KB page?

If you append variable-length rows sequentially from the top of the page, updating or deleting a row in the middle forces you to shift all subsequent row bytes, fragmenting memory.

Database engines solve variable-length storage using Slotted Pages.

=====================================================================
                      16KB SLOTTED PAGE ANATOMY
=====================================================================
[ Page Header ]  (38 bytes: LSN, Page Type, Free Space Pointer, etc.)
---------------------------------------------------------------------
[ Slot 0 Pointer ]  (Offset: 16300, Length: 84)   ===> Grows DOWN
[ Slot 1 Pointer ]  (Offset: 16180, Length: 120)  |
[ Slot 2 Pointer ]  (Offset: 16000, Length: 180)  v
---------------------------------------------------------------------
                       <--- FREE SPACE GAP --->
---------------------------------------------------------------------
                                                  ^
[ Tuple Data 2 ]    (Offset: 16000)               |
[ Tuple Data 1 ]    (Offset: 16180)               | Grows UP
[ Tuple Data 0 ]    (Offset: 16300)               |
=====================================================================

The Three Page Regions:

Page Header & Slot Array (Grows Downward):
- Header: Stores page metadata (Page Number, Log Sequence Number LSN, Free Space Pointers, Transaction Flags).
- Slot Array (Line Pointers): An array of 2-byte or 4-byte offset pointers extending from the top down. Slot 0 points to physical byte position 16,300 inside the page.
Tuple Payload Space (Grows Upward):
- Raw row byte payloads (column values, null bit maps, record headers) are inserted from the bottom of the page moving upward.
Free Space Gap:
- The unallocated memory space sitting between the downward-growing Slot Array and the upward-growing Tuple Payloads.

Record IDs (RID) / Tuple IDs (TID)

Because the Slot Array holds the offset pointer to a tuple’s physical byte location, a row’s address within a database is represented as a 64-bit Record ID:

$\text{Record ID (RID)} = (\text{Page Number}, \text{Slot Index})$

RID (Page 42, Slot 2)
  |
  v
Look up Page 42 on disk/buffer pool
  |
  v
Read Slot Array Index 2 ---> Physical Offset 16,000 inside Page 42

Why Slotted Pages Handle Deletions and Updates Easily

If Row 1 ("Alex") is updated to a longer name ("Alexander The Great"), the storage engine writes the updated tuple data at the bottom of the Free Space Gap and updates Slot 1 Pointer to point to the new physical offset.

The Record ID (Page 42, Slot 1) remains completely unchanged! Secondary indexes pointing to (Page 42, Slot 1) do not need to be rewritten.

If a row is deleted, its slot entry is marked as dead. When free space grows fragmented, the database engine defragmenter reorganizes tuple payloads within the 16KB page in RAM in a single contiguous step.

Heap File Layout: Managing Pages Across a Table

A table consists of thousands of pages. How does the storage engine locate a page with enough free space to store a new row?

A Heap File is an unordered collection of data pages. Storage engines manage heap file pages using two approaches:

1. Linked List Heap Files

The heap file header page maintains two doubly linked lists of pages:

A linked list of Full Pages.
A linked list of Pages with Available Free Space.

[ Header Page ] 
   |
   +---> Full Pages List:      [ Page 1 ] <---> [ Page 4 ] <---> [ Page 7 ]
   |
   +---> Free Space List:     [ Page 2 ] <---> [ Page 3 ] <---> [ Page 5 ]

When inserting a new row, the engine fetches the first page from the Free Space List.

2. Page Directory Files (Modern Standard)

Modern engines (such as PostgreSQL and InnoDB) use a Page Directory.

The directory is a dedicated page (or set of pages) that maintains an array listing every page in the table file alongside a bitmask estimating its remaining free space capacity:

PAGE DIRECTORY PAGE
Page Number | Free Space Available
------------|----------------------
Page 1      | 0 bytes (FULL)
Page 2      | 4,120 bytes (25% free)
Page 3      | 12,000 bytes (75% free)

When inserting a row requiring 500 bytes, the storage engine scans the Page Directory in RAM, finds Page 2, and jumps directly to Page 2 without scanning physical data pages.

Quick Summary

Data files are organized into fixed-size pages (16KB in MySQL InnoDB, 8KB in PostgreSQL).
Slotted Page architecture separates fixed-size offset pointers (Slot Array) from variable-length row data (Tuple Payloads).
Record IDs (RID = PageNo + SlotIndex) remain stable even when tuple bytes move inside a page during updates.
Page Directories track free space availability across table pages, eliminating linear disk searches during insertions.

References & Further Reading

Oracle Corporation. MySQL 8.0 Reference Manual: InnoDB Storage Engine Architecture & Page Structure. MySQL Documentation.
PostgreSQL Global Development Group. PostgreSQL 16 Documentation: Chapter 73 Database Physical Storage (Page Layout). PostgreSQL Docs.
Garcia-Molina, H., Ullman, J. D., & Widom, J. (2008). Database Systems: The Complete Book (2nd Edition). Pearson.