Slotted Page Architecture

From B-trees to bytes

The previous chapter built a B-tree as an in-memory structure of nodes and pointers. A real database can't keep everything in RAM — it stores the tree on disk, in fixed-size chunks called pages (SQLite uses 4096 bytes by default, matching the OS's memory-page size, which is exactly why 4096 shows up in this exercise). Every node of the B-tree, every table's rows — everything — has to be packed into these fixed-size byte arrays. This lesson is about the layout that makes that packing possible: the slotted page.

Why not just append cells one after another?

The obvious approach — write cells back-to-back as they arrive — has a fatal flaw: cells have variable length (a TEXT value can be 3 bytes or 300), so you can't compute where cell #5 starts without scanning through cells #1–4 first. You need O(1) access by slot index. The slotted page solves this by separating where a cell's bytes live from the order you look cells up in.

The layout

A slotted page is divided into three regions:

+----------------+----------------------+------------------+----------------------+
|  page header   |  slot / pointer array | <- free space -> |     cell data ->     |
+----------------+----------------------+------------------+----------------------+
 grows not at all      grows rightward                          grows leftward

• Header (fixed size, front of the page): page type, number of cells currently stored, and a pointer to where free space begins (often called the "cell content start" offset).
• Slot array (grows left → right, immediately after the header): one fixed-size entry per cell, typically just a 2-byte offset pointing into the cell-data region. Slots are kept in the same order you want to iterate cells — for a B-tree leaf, that's key order.
• Cell data (grows right → left, from the end of the page backward): the actual variable-length bytes — key, value, and any per-cell metadata (like value length, needed since cells aren't fixed size).
• Free space is whatever's left between the end of the slot array and the start of cell data. As you insert, the slot array eats into free space from the left and cell data eats into it from the right; when they'd collide, the page is full.

Why grow from opposite ends?

This is the classic trick that makes slotted pages efficient: the slot array and the cell data grow toward each other. You never need to know the final number of cells in advance, and both regions can grow independently without ever needing to relocate the other — until they actually meet, which is the real, unambiguous "page full" condition.

Insert algorithm

function insert(page, key, value):
    cell_bytes = serialize(key, value)
    needed = cell_bytes.length + SLOT_SIZE
    if needed > page.free_space:
        return ERR "page full"
    write cell_bytes at (cell_content_start - cell_bytes.length)
    cell_content_start -= cell_bytes.length
    insert a new slot pointing at cell_content_start,
        in the correct sorted position in the slot array
    num_cells += 1

Note the slot array insert should keep slots sorted by key so lookups can binary-search the slot array directly (compare the key stored at each slot's target offset) without touching the cell data region except to compare/return the winning cell.

Get / delete and fragmentation

PAGE GET <key> binary-searches the slot array by key, then follows the winning slot's offset into the cell-data region to read the value.

Deleting a cell is where slotted pages get subtle: if you just remove its slot, the bytes it pointed to become a hole in the middle of the cell-data region — free space that isn't contiguous with the "real" free space in the middle of the page. Many real engines tolerate this fragmentation and periodically compact the page (rewrite all cells contiguously from the end, in slot order, resetting the free-space pointer) rather than fixing it on every delete. For this exercise, decide up front whether PAGE INFO's free:<bytes> reports only the contiguous middle gap or the true total including holes — and be consistent, since your later Overflow Pages lesson depends on knowing exactly how much a page can still hold.

Edge cases

• A cell exactly large enough to hit the boundary between free-space-available and page-full — off-by-one here silently corrupts the next insert.
• Inserting a key that already exists (update-in-place vs. reject, depending on your spec).
• PAGE INFO after deletes, if you don't compact — free space should reflect reality, not just "started full, now zero."