What is a Slotted Page?
A slotted page is the standard internal layout of a database page (typically 4 KB or 8 KB). It solves a fundamental problem: how to store variable-length records in a fixed-size block of bytes while keeping record IDs stable.
Page structure
A slotted page has three regions:
-
Page header (at the very top) — contains metadata:
- Page ID — identifies this page in the file.
- Checksum — detects corruption.
- Free space offset — pointer to the start of free space.
- Slot count — how many slots are in the slot array.
-
Slot array (grows downward from the header) — an array of (offset, length) pairs. Slot 0 is right after the header, slot 1 is next, and so on. Each entry tells you where in the page the corresponding record starts and how many bytes it occupies.
-
Records (grow upward from the bottom of the page) — the actual row data is packed starting from the end of the page, growing toward the header.
-
Free space — the gap between the end of the slot array and the start of the records. As long as this gap is positive, the page can accept more data.
Inserting a record
- Append a new slot entry to the slot array (grows down).
- Write the record data at the current free-space boundary (grows up from the bottom).
- Update the free space offset in the header.
Deleting a record
Set the slot entry to a special "empty" marker (e.g., offset = 0, length = 0). The record bytes become dead space. To reclaim this space, perform page compaction: slide all live records toward the bottom of the page, update their slot offsets, and reclaim the fragmented space into one contiguous free block.
Why this design?
- Stable Record IDs: external references (indexes) point to a slot number, not a byte offset. When compaction moves a record, only the slot entry changes — the slot number stays the same.
- Variable-length records: the (offset, length) indirection handles records of any size.
- Efficient space management: free space is always a single contiguous region (after compaction).
Complexity
| Operation | Time |
|---|---|
| Insert | O(1) |
| Get by slot | O(1) |
| Delete | O(1) |
| Compaction | O(n) |
where n is the number of live records on the page.
Real-Life: PostgreSQL Page Layout
PostgreSQL uses exactly this slotted page design for its 8 KB pages. Here is how it maps:
- Page header (24 bytes): includes pd_checksum, pd_lower (end of slot array), pd_upper (start of free space from bottom), pd_special (start of special space for indexes).
- Line pointers: PostgreSQL's name for the slot array. Each is 4 bytes: a 15-bit offset, a 2-bit status flag (normal, redirect, dead, unused), and a 15-bit length.
- Tuples: stored from the bottom of the page upward.
Free space = pd_upper - pd_lower. If a new tuple plus a 4-byte line pointer exceeds this, the page is full.
VACUUM reclaims dead tuples by compacting the page: it slides live tuples down, updates line pointers, and adjusts pd_upper. Indexes still point to the same line-pointer slot number, so they remain valid.
This layout is also used (with variations) by MySQL InnoDB, SQLite, and Oracle.