Page Layout and Slotted Pages

You already know how to index a byte slice and encode a small integer. This module connects those operations to a storage-engine problem: moving a record must not invalidate the identifier stored in an index.

By the end, you should be able to compute insertion capacity, trace a deletion and compaction byte by byte, and explain why a slot number survives a move.

1. Separate identity from location

Imagine an index storing key → byte offset. Deleting an earlier record and packing the remaining bytes changes the offsets, so every affected index entry would need repair. Instead store key → (page ID, slot ID). The slot contains the record's current offset and length. Compaction changes that descriptor while preserving the slot ID of each live record.

The exercise uses this specific layout:

0                        freeStart      freeEnd                      size
| record bytes and holes | unused gap   | slot N-1 | ... | slot 0 |

Each slot uses four bytes: a little-endian uint16 offset followed by a little-endian uint16 length. Slot s begins at size - 4*(s+1). freeStart, freeEnd, and the slot count live in the Go struct; this exercise does not reserve an on-page header. Real formats may reserve headers and grow the regions in the opposite direction. PostgreSQL, for example, also uses item identifiers to preserve indirection when items move, but its layout is different. PostgreSQL page layout.

2. Work a 32-byte page by hand

Use half-open byte ranges: [0,6) means bytes 0 through 5. Records are nonempty; length zero marks a deleted slot. Every insertion allocates a new slot, even after deletion. No implicit compaction or slot reuse occurs.

Operation	Live record ranges	Directory start	Data end	Contiguous free bytes
New page	none	32	0	32
Insert ABCDEF, slot 0	s0: [0,6)	28	6	22
Insert wxyz, slot 1	s0: [0,6), s1: [6,10)	24	10	14
Insert 12345, slot 2	s0: [0,6), s1: [6,10), s2: [10,15)	20	15	5
Delete slot 1	s0: [0,6), s2: [10,15)	20	15	5
Compact	s0: [0,6), s2: [6,11)	20	11	9

Before deletion, slot 1's descriptor at bytes [24,28) is 06 00 04 00. Deletion changes its length to zero, leaving an unused four-byte payload hole. It does not remove the descriptor or move either free-space boundary.

After compaction, slot 2 is still slot 2. Its descriptor at [20,24) changes from 0a 00 05 00 to 06 00 05 00. Calling Get(2) still returns 12345; Get(1) reports absence. Renumbering slot 2 to slot 1 would break the index.

3. Space includes metadata

An insert of length L needs L + 4 contiguous bytes. Immediately after the deletion above, a five-byte insert needs nine bytes but the gap has only five: it must fail without changing the page. After compaction, the gap is exactly nine bytes, so the same insert succeeds as slot 3 and leaves zero free bytes.

The four-byte hole was reclaimable payload space, not immediately usable contiguous space. After deleting every record and compacting, the descriptors still occupy space. With four allocated slots on this page, the empty payload region has 32 - 4*4 = 16 bytes available. Slot reuse would be another policy; it would need rules for stale record IDs and is outside this exercise.

4. Derive the operations from invariants

Maintain 0 <= freeStart <= freeEnd <= size and freeEnd = size - 4*slotCount. Every live range stays below freeEnd; live ranges do not overlap. A deleted descriptor has length zero.

For insertion, decide whether the whole payload plus descriptor fits before changing any state. Copy the payload, write the new descriptor, and update the boundaries. FreeSpace() reports freeEnd - freeStart, including no holes.

For deletion, validate the slot and mark its length zero. Deleting an invalid or already deleted slot returns false. Get must return a copy: modifying the caller's result must not silently change the stored record.

For compaction, start with an empty destination payload region. Visit slots in slot-ID order, copy each live record to the next destination position, and rewrite that slot's offset. Keep the empty descriptors. A fresh page-sized buffer makes source/destination overlap easy to reason about; an in-place version needs an equally careful movement argument. Running compaction twice must leave the same logical records and free-space count.

5. Predict before coding

A 40-byte page receives records of lengths 7, 5, and 4. Then slot 0 is deleted. Predict FreeSpace() before and after compaction, the new offset of slot 2, and whether an eight-byte record can then be inserted.

Check the arithmetic

Three descriptors occupy 12 bytes. The old data end is 16, so deletion leaves 40 - 12 - 16 = 12 contiguous bytes. Compaction keeps nine payload bytes, giving 40 - 12 - 9 = 19. Slot 1 moves to offset 0; slot 2 moves to offset 5. The new record needs 8 + 4 = 12 bytes, fits as slot 3, and leaves seven bytes.

Now implement Slotted Page. Start with insert/get, add deletion without moving bytes, then add compaction. Check exact fit, one byte too large, repeated deletion, copy ownership, and stable IDs. The checkpoint tests a fresh history.