Skip to main content

Pages, Records, Heap Files, Slotted Pages

What This Concept Is​

The database file is not a stream of rows. It is a sequence of fixed-size pages. Each page holds some number of records (tuples, rows). A heap file is simply a file of pages with no imposed order: new rows go wherever there is room.

Inside a page, records are usually packed with a slotted-page layout, also called a "slot directory" layout:

+---------------------------------------------------------+
| Page header (page id, free-space ptr, slot count, ...)  |
+---------------------------------------------------------+
| Slot 0 | Slot 1 | Slot 2 | ... -> (grows right)         |
+---------------------------------------------------------+
|                    <- free space ->                     |
+---------------------------------------------------------+
| ... <- (records grow left)  | Rec 2 | Rec 1 | Rec 0 |   |
+---------------------------------------------------------+

The slot directory at the top holds (offset, length) pairs. The records themselves are packed from the bottom. The gap in the middle is the free space where new records and new slots meet.

Why this layout? Because records can be variable length, but the engine must give each row a stable identifier, the record id (RID) of the form (page_id, slot_id). The slot is a stable handle: if a record grows, the engine can move the record bytes within the page and update the slot offset without changing the RID.

Why It Matters Here​

Every index in the rest of this module eventually points at a record. That pointer is either an RID or a primary key. If slot numbers were not stable, every index would have to be rewritten every time a row was updated. The slotted page is what makes indexes practical on variable-length rows.

It also explains things that otherwise look mysterious:

  • why a DELETE leaves a "tombstone" slot (the slot stays; the record is marked dead so the RID survives)
  • why UPDATE on a variable-length row can cause a row migration to another page, leaving a forwarding pointer behind
  • why VACUUM / reorganization is a real operation and not paranoia

Concrete Example​

Start with an empty 8 KB page. Insert three rows:

+ Header | Slots: [] | free: 8100 | records: []
Insert R1 (50B):
  record stored at offset 8050 (bottom grows up? actually bottom-packed)
  slot 0 = (offset=8050, length=50)
Insert R2 (120B):
  record at offset 7930, slot 1 = (7930, 120)
Insert R3 (80B):
  record at offset 7850, slot 2 = (7850, 80)

RIDs are (page_42, 0), (page_42, 1), (page_42, 2). Now update R1 from 50B to 200B. There is still room, so the engine allocates 200B at the current free pointer and updates slot 0's offset to the new location. The old 50B hole is reclaimed next compaction. The RID (page_42, 0) is unchanged, so every index entry pointing at it is still valid.

If the row instead had to grow to 5000B and this page only had 200B free, the engine writes R1 to another page and leaves a forwarding pointer in slot 0. A subsequent lookup of (page_42, 0) follows the pointer. That is one extra I/O per access.

Common Confusion / Misconception​

"A row is stored in one place." Not reliably. Between row migration, TOAST/large-object offloading, and update-in-place variants, a row's bytes may live on another page or even another file. The RID is the stable handle; the bytes are allowed to move.

"Heap files are sorted." They are not. The word "heap" here means unordered pile of pages, unrelated to the heap data structure. Rows land wherever the engine finds room.

How To Use It​

When reasoning about a storage engine, keep three levels in mind:

  1. the file (a sequence of pages on disk)
  2. the page (header + slot directory + packed records + free space)
  3. the record (columns encoded per the table schema)

For any operation, ask:

  • which pages does this touch?
  • which slots are created, moved, or tombstoned?
  • will this cause a row migration?

Check Yourself​

  1. Why does the slot directory grow from one end of the page and records grow from the other?
  2. What does DELETE actually change on a page, and why does the slot usually remain?
  3. Why does an update that makes a row larger sometimes trigger a second I/O on the next read?

Mini Drill or Application​

Draw a single 4 KB slotted page for this sequence and note free space after each step:

  1. INSERT three rows of 200, 500, 300 bytes.
  2. UPDATE the first row to 250 bytes.
  3. DELETE the second row.
  4. INSERT a new row of 400 bytes.
  5. UPDATE the first row to 3500 bytes (does it fit? what happens if not?).

State the RIDs after each step and whether any are invalidated.

Read This Only If Stuck​