Slotted Page Layout: Row Storage, Slot Directory, and In-Page Compaction

What It Is and the Problem It Solves

A storage engine reads and writes the disk in fixed-size blocks, typically 4-16 KB, because that is the unit the buffer pool, WAL, and I/O subsystem operate on. But real rows are variable-length: a VARCHAR, a NULL bitmap, a TEXT column, or a JSONB blob all make tuples different sizes, and they grow or shrink on UPDATE. Packing such records naively creates two problems. First, deleting a middle tuple leaves a hole (fragmentation). Second, if a record's address is a raw byte offset, moving bytes to reclaim that hole would invalidate every index entry and foreign pointer that referenced it.

The slotted page solves both with one idea: separate the logical address from the physical location. Each record is reachable through a slot, a fixed-size directory entry holding the tuple's current byte offset and length. External references store the slot number, never the offset. The engine is then free to relocate the actual bytes inside the page at will, updating only the private slot entry. This is the workhorse layout for heap files and B-tree leaf pages in nearly every relational database.

How It Works, Step by Step

A slotted page has three regions. At the top sits a small page header (checksum, LSN, free-space pointers, slot count). Just below it, the slot directory grows downward: an array of entries, one per record, each typically holding an offset and a length (in PostgreSQL, a 4-byte ItemId). From the bottom of the page, the actual tuple data grows upward. The gap between the last slot and the highest tuple is the free space.

INSERT(record r):
  if free_space < len(r) + sizeof(slot): return PAGE_FULL
  data_top    -= len(r)          // carve space from the bottom
  write r at offset data_top
  slot[n]     = (data_top, len(r))
  n           += 1
  return slot_number n-1

DELETE(slot i):
  mark slot[i] as dead (offset = 0 / tombstone)
  // bytes stay until compaction; slot number is NOT reused

LOOKUP(slot i):
  (off, len) = slot[i]
  return bytes[off .. off+len]     // O(1)

Deletes leave a tombstone slot so the slot number is never reused (dangling index entries must resolve to "dead"). When accumulated holes prevent an insert despite enough total free bytes, the page runs compaction: slide all live tuples together, rewrite each slot's offset, and coalesce the free space into one contiguous block.

Complexity and a Worked Step Trace

Let the page hold up to n records. Lookup by slot number is O(1): index the directory, read (offset, length), return the bytes. Insert is O(1) amortized (write at the data pointer, append a slot). Delete is O(1) (tombstone the slot). Compaction is O(n) in the live tuple count and is triggered lazily, only when fragmented free space blocks an insert. Space overhead is one slot per record: 4 bytes in PostgreSQL, a few bytes in SQLite's cell-pointer array, negligible against typical row widths.

Page (100 bytes, header=10). Insert A(20), B(15), C(10):
  slots:  [ (80,20) (65,15) (55,10) ]        // grows down from 14
  data:   ...............[C 55-65][B 65-80][A 80-100]
  free = 55 - (10 + 3*4) = 33 bytes

DELETE slot 1 (B):  slot[1] = TOMBSTONE
  live bytes now A(20)+C(10)=30, but the 15-byte B-hole is trapped.

INSERT D(28):  33 free >= 28+4? contiguous free is only 33-15=... 
  fragmented -> COMPACT: slide C up beside A, rewrite slot[2].
  Now one 45-byte free block -> D fits, gets slot 3.

The invariant the engine maintains: free_space = data_top - (header_end + num_slots * slot_size), and every live slot's [offset, offset+length) range is disjoint from every other live tuple.

Real-System Usage

PostgreSQL is the canonical example: every heap page is slotted, with an array of 4-byte ItemId line pointers and tuples filling from the end. A row's address is its ctid = (block_number, item_offset), the tuple identifier that indexes point to. VACUUM reclaims dead tuples and can trigger page compaction; pageinspect lets you read the raw slot array. SQLite uses the same idea on B-tree pages: a cell-pointer array at the top, cells (rows) packed from the bottom, and freeblocks tracking reclaimable holes, defragmented on demand.

IBM DB2, Oracle (row directory in each block), SQL Server (slot array at the end of each 8 KB page), MySQL/InnoDB (records linked in a page with a directory of slots for binary search) all use variants. The stable slot number is what makes secondary indexes practical: an index entry can store a compact RID/TID and survive intra-page reorganization. It is one of the most widely deployed data-layout patterns in production software.

Comparison to Alternatives and the Tradeoff

The simplest alternative is a fixed-length slot array: divide the page into equal cells and index directly. It has no fragmentation and no directory offsets, but forces padding to the widest row, wasting space and failing outright for TEXT/BLOB columns. The slotted page trades that padding for one indirection and occasional O(n) compaction, in exchange for true variable-length support.

A packed append heap (no directory, addresses are byte offsets) is compact but brittle: any compaction rewrites external pointers, so indexes must be rebuilt or fixed up. Log-structured merge (LSM) storage sidesteps in-page mutation entirely by writing immutable sorted segments and compacting in the background, which excels at write-heavy workloads but pays read amplification across levels and needs Bloom filters to prune. The slotted page's sweet spot is read-mostly, update-in-place workloads where stable record identity and O(1) point lookup matter, exactly the profile of a classic B-tree-indexed relational table.

Pitfalls and Significance

The chief failure modes are subtle. Slot-number reuse is dangerous: reuse a tombstoned slot for a new row and a stale index entry now silently points at the wrong tuple; engines therefore keep tombstones until it is provably safe (PostgreSQL waits for VACUUM after no transaction can see the dead tuple). Grow-in-place UPDATE is a classic trap: if a row grows past its old length, it may not fit its hole. The engine either compacts, or moves the tuple and leaves a forwarding pointer (a redirect slot), which can degenerate into a chain and hurt locality (Oracle's "row migration/chaining," MySQL's overflow pages). Fragmentation and lazy compaction mean total free space can exceed the largest usable contiguous run.

Its significance is durability of design: proposed in the classic transaction-processing literature (Gray and Reuter's Transaction Processing, 1993, codifying practice from 1970s System R and IMS) and canonized in Hellerstein, Stonebraker, and Hamilton's Architecture of a Database System (2007), the slotted page has survived five decades essentially unchanged because indirection cleanly decouples what a record is from where its bytes are.

Slotted page vs. alternative in-page record organizations

Layout	Variable-length records	Record address stability	In-place compaction	Lookup cost
Slotted page	Yes, natively	Stable (slot number)	Yes, transparent to indexes	O(1) via slot directory
Fixed-length array of slots	No (padding wastes space)	Stable (array index)	N/A (no fragmentation)	O(1) direct index
Append-only log / packed heap	Yes	Fragile (byte offset)	Requires rewriting pointers	O(1) but pointers break on move
Log-structured (LSM) segment	Yes	Immutable segments	Via background compaction/merge	O(log n) across levels