Slotted Pages: Variable-Length Records in Fixed Pages

The B-tree chapter kept nodes in memory. A database cannot: disks read and write fixed-size blocks, so every table row and index entry lives inside a page, a block of bytes of one fixed size (SQLite defaults to 4,096). After this lesson you can store, read, delete and compact variable-length records in a page whose bytes you can print and check by hand.

The problem

Rows have different lengths ('Al' and 'Alexandra'), so you cannot find record 5 by arithmetic. And once other structures (an index entry, a B-tree pointer) remember "record 5", that number must keep working when records are added, removed or moved. The classic answer is the slotted page: a small array of slots gives records stable numbers, and each slot says where its record's bytes currently are.

The layout

All numbers are 2 bytes, little-endian (low byte first).

The slot array grows up from the front, the cells grow down from the back, and the free space is the gap between them: cell start - (4 + 2 * slot count). The page is full when the gap cannot hold the next record.

A page of 32 bytes after PAGE INSERT hi:

offset  bytes        meaning
0       01 00        slot count = 1
2       1c 00        cell start = 28
4       1c 00        slot 0 -> offset 28
6..27   00 x 22      free space (22 bytes)
28      02 00 68 69  cell: length 2, then 'h' 'i'

Insert

A record needs 2 + length bytes for its cell, and 2 more for a new slot unless a deleted slot can be reused (lowest number first). If the total is larger than the free gap, the insert fails with ERR page full; nothing changes. Otherwise write the cell immediately below the current cell start, move cell start down, and point the slot at it. An exact fit works: with a free gap of 28 bytes, a 24-byte record needs 26 + 2 = 28 and succeeds, leaving 0.

Delete leaves a hole

Deleting a record sets its slot to 0. The cell's bytes stay where they were; only the slot says they are dead. Slot numbers of other records do not change, which is the whole point. But the dead cell is now a hole inside the cell area: bytes that are not free space, because free space is only the contiguous gap. So a page with room for 20 bytes in total may refuse a 12-byte record whose gap is only 8.

Compaction

PAGE COMPACT slides every live cell to the end of the page, in slot order (the lowest live slot ends up last in the page), zeroes everything after the slot array, and updates the cell start and each slot's offset. Slot numbers stay the same; holes disappear, and the reclaimed bytes join the gap. Real engines compact lazily, only when an insert would otherwise fail; here it is a command so you can see the effect.

Commands

Other errors: ERR no page before the first NEW, ERR size must be 16 to 4096, ERR usage: ..., ERR unknown command: ....

Common mistakes

• Forgetting the slot's 2 bytes in the space check, which overruns the gap by one slot at the boundary.
• Writing a cell at the old cell start instead of below it: the first record then overwrites the page's last byte.
• Zeroing or moving cells on delete. Delete only clears the slot; PAGE DUMP shows the stale bytes.
• Renumbering slots in compact. Slot numbers are identities.

Your exercise

The starter handles parsing, INFO and DUMP. You write insert_cell, read_cell, delete_cell and compact. The mistake to avoid: counting only the cell's size when checking whether the record fits.