Slotted Pages — Fixed-Size Page Layout

Real databases don't store data in language-level arrays — they use pages (also called blocks), which are fixed-size chunks of memory that map directly to disk blocks.

Why Pages?

Disks read and write in fixed-size blocks (typically 4KB or 8KB). By making our storage unit match the disk block size, we get:

1. Efficient I/O: One page = one disk read/write
2. Cache-friendly: Pages fit in OS page cache
3. Predictable sizing: Easy to manage buffer pools

SQLite uses 4096-byte pages by default. PostgreSQL uses 8192 bytes.

Slotted Page Layout

A slotted page has three regions:

+--------------------------------------------------+
| Page Header (type, cell count, free space ptr)   |
+--------------------------------------------------+
| Cell Pointer Array (grows →)                      |
| [offset1] [offset2] [offset3] ...                |
+--------------------------------------------------+
|                                                    |
|              Free Space                            |
|                                                    |
+--------------------------------------------------+
| ... [Cell 3 data] [Cell 2 data] [Cell 1 data]   |
|                      Cell Data (← grows)          |
+--------------------------------------------------+

Cell pointer array grows from left to right. Each entry is an offset pointing to where the cell's data is stored.

Cell data grows from right to left. New cells are appended at the end of used space.

Free space is the gap in the middle that shrinks as data is added.

Why This Design?

The beauty of slotted pages is that cell pointers can be reordered without moving data. To keep cells logically sorted by key, just rearrange the pointer array. The actual cell data stays put.

This is critical for B-tree operations where we frequently insert keys in sorted order.

Page Header

Offset  Size  Field
0       1     Page type (leaf=0x0D, internal=0x05)
1       2     Number of cells
3       2     Offset to first byte of free space
5       2     Offset to first cell (rightmost data)

Cell Format

Each cell contains:

• Key (for B-tree ordering)
• Payload size (variable-length prefix)
• Payload data (the actual row data)

Free Space Management

When a cell is deleted, its space is added to a free list within the page. New inserts first check the free list before consuming free space from the middle gap.

How SQLite Structures Pages

SQLite's page format (btreeInt.h) is almost exactly this slotted design. Each B-tree page stores cells containing rowid + row data. The cell pointer array at the beginning of the page is kept sorted by key for binary search.

Your Task

Build a fixed-size page (4096 bytes simulated) with insert, get, and info commands that track cells and free space.