Slotted Pages

If every record were 80 bytes, a page would be an array: record k at 24 + 80k, no directory, no headers, deletion by a bitmap. Rows are not like that. A TEXT column makes every record a different length, an UPDATE makes the same record a different length tomorrow, and NULL makes a column vanish. So a page cannot compute where record k is; it has to *store* where record k is. And whatever it stores is referenced from outside — every index entry on the table holds a record address — so the answer must survive the page being edited.

The naive layout, records packed from the front, fails on exactly that. Deleting record 3 leaves a permanent hole or shifts records 4 through 99 and breaks every pointer to them. The requirement is a name for a record that does not change when its bytes move. That name is the slot.

A slotted page is three regions and two pointers. The header (24 bytes in PostgreSQL) holds the checksum, the LSN, flags, and lower and upper. The slot directory starts right after the header and grows *down* the page: slot i is at 24 + 4i and holds the record's offset and length (and two flag bits). The records start at the *end* of the page and grow *up*: the first record inserted is at 8192 − len, the next just below it. Between lower (end of the directory) and upper (start of the records) lies the free space, and upper − lower is exactly how much a new record plus its slot may take.

The two regions grow towards each other so that neither has to be sized in advance: a page of 100 short records and a page of 12 long ones use the same layout. A record is addressed as (page, slot); the slot's offset is private to the page. The consequence that makes everything else possible: the page may move a record's bytes as long as it updates the slot. Nobody outside notices.

Insert a record of len bytes: check upper − lower ≥ len + 4; write the bytes at upper − len; set upper to that; append a slot (upper, len); lower += 4. Cost: the record plus four bytes, and no other record moved. Delete slot i: set its flags to dead, zero its offset and length. The bytes stay where they are — a hole — and the slot stays in the directory, because slot i may still be named by an index entry or by a concurrent scan, and "dead" is the correct answer to give them. Reusing the slot number for a different record would make those references silently point at the wrong row.

Update is where the design earns its keep. If the new version is the same size or smaller, overwrite in place (the tail becomes a small hole). If it is larger and the record happens to border the free space, extend it. Otherwise, write the new version into the free space and re-point the slot: slot i now says (new offset, new length), the old bytes are a hole, and every index entry that says (page, slot i) is still correct. The record moved; its name did not.

Every delete, shrink and move leaves a hole, and holes are useless until they are adjacent to the free space. A page therefore has two numbers that both deserve the name "free": the contiguous upper − lower, which an insert can use, and the fragmented bytes scattered in holes, which it cannot. A page with 7 KB of holes and 60 bytes between lower and upper rejects a 100-byte insert. The page inspector shows both, and the moment an insert fails with plenty of fragmented space is the moment compaction is invented.

Compaction slides the live records together at the end of the page — highest offset first, so the picture keeps its order — and rewrites the offset in each slot. upper moves down to the new start of the records; the holes are gone; the contiguous free space is now everything that was free. Dead slots stay dead and keep their numbers. No index, no scan, no other page is involved: compaction is a purely local operation, which is why it can be done lazily and cheaply, typically the first time an insert or update would otherwise fail.

What compaction does not do is shrink the slot directory. Dead slots are only reclaimed when it is provably safe — in PostgreSQL, when VACUUM has confirmed no index entry points at them, after which they become LP_UNUSED and may be reused; the last slots can be truncated. A table with heavy delete churn on a few pages can end up with pages that are mostly directory.

PostgreSQL never overwrites a live tuple, because an older transaction may still need to see it: every update is an insert of a new version plus an xmax on the old one. The question is only *where* the new version goes. If no indexed column changed and the page has room (after pruning its holes), the new tuple goes on the same page and the old tuple's t_ctid points to it: a heap-only tuple (HOT). Indexes still point at the old slot, and a lookup follows the chain — so no index is touched by the update at all. This is the single biggest reason to keep fillfactor below 100 on hot tables: room for HOT versions on the same page.

If the new version does not fit even after PageRepairFragmentation, or an indexed column changed, it goes to another page chosen from the free-space map. The old tuple stays, dead, with its t_ctid forwarding to the new location, and *every* index on the table gets a new entry pointing at it. The forwarding pointer keeps in-flight scans and stale index entries correct; VACUUM eventually removes the dead tuple and the index entries that led to it. Values that would not fit in a page at all never reach the page: beyond about 2 KB, TOAST compresses them or moves them to a separate table and leaves a pointer.

InnoDB rows live in the leaf pages of the clustered index, in primary-key order, linked by each record's next_record offset; the page directory at the *end* of the page holds 2-byte slots that each own a group of 4–8 records, so a lookup binary-searches the directory and then walks a few records. An update that does not change the row's size is done in place — the previous version has already been copied to the undo log, and DB_ROLL_PTR points at it, so no second copy is needed in the page. An update that changes the size is done as a delete and reinsert within the page, which keeps key order; if the reinsert does not fit, InnoDB reorganizes the page (its compaction) and tries again.

When even a reorganized page cannot hold the row, "another page" means a B+ tree page split: half the records move to a new page and the parent gets a new separator key (B+ Tree Internals: Pages, Splits, Merges). Secondary indexes do not notice — they store the primary key value, not a page and slot — so a row moving between clustered-index pages costs no secondary-index maintenance, the mirror image of PostgreSQL's cost. InnoDB reserves 1/16 of each page on sequential inserts precisely so that later size-changing updates usually stay put; columns that outgrow the row go to overflow pages behind a 20-byte pointer.