Page Layout: Identity and Bytes

An index stores (page, slot). A slot stores (offset, length). Moving a live record changes its offset, not its slot ID.

Exercise layout

• Payload from the front; four-byte descriptors from the back.
• Slot s starts at size - 4*(s+1).
• Struct metadata uses no page bytes in this model.
• Every insert appends a slot; length zero means deleted.

Trace a 32-byte page

Insert lengths 6, 4, 5: payload end 15, directory start 20, gap 5. Delete slot 1: four-byte hole, gap still 5. Compact: payload end 11, directory start 20, gap 9. Slot 2 moves from offset 10 to 6; its ID remains 2.

Payload plus descriptor

A five-byte record needs nine bytes. It fails before compaction and fits exactly afterward. Failed insertion leaves state unchanged. Deleting all records still leaves the allocated slot directory.

Reconstruct, then implement

For a 40-byte page, insert lengths 7, 5, 4 and delete slot 0. Predict free space, offsets after compaction, and an eight-byte insert. Verify copy ownership, exact fit, repeated delete, and compaction idempotence.