Page Layout and Slotted Pages

Why this module exists

Disks and SSDs deal in fixed-size pages. A page must store variable-length records while supporting insert, delete, and update. The slotted page format is the canonical solution.

1) Slotted page structure

A typical page layout:

• Header: free space pointers
• Data region: records packed from the front
• Slot directory: (offset, length) pairs packed from the back

The header tracks:

• freeStart: end of packed records
• freeEnd: start of slot directory

A page is full when freeEnd - freeStart cannot fit a new record + slot entry.

2) Why slots matter

Slots give each record a stable ID even if the record is moved during compaction. This allows indexes to store a RID (page ID + slot ID) while the record moves within the page.

3) Fragmentation and compaction

Deletes leave holes. Without compaction, insertions fail early. A good page implementation can compact data and update slot offsets without changing slot IDs.

What you will build

• A slotted page with insert, delete, get, free space, and compaction.

Key takeaways

• Slotted pages separate record identity from physical layout.
• Fragmentation must be handled explicitly.
• Invariants are about offsets, not just bytes.