Slotted Page Structure: Stable Pointers on Disk

Why it exists

Storing records sequentially in a database page is simple but inefficient. When a record is deleted, it leaves a gap. To reclaim that space, all subsequent records must be shifted, which is a slow operation. More importantly, this reshuffling invalidates any pointers from indexes or other structures that were pointing to the moved data.

The mental model

Imagine a fixed-size block of memory, like a 4KB page, as a bookshelf. A slotted page layout puts the books (the actual data) on the shelf starting from the right side. A separate card catalog (the pointers, or 'slots') is kept on the left side. As you add books, you also add a card to the catalog. The empty space in the middle shrinks from both sides. This way, you can remove a book and its card without shifting all the other books.

How it works

A slotted page is divided into three main regions that grow toward each other. First, a fixed-size header at the beginning of the page stores metadata like the page ID and the boundaries of the free space. Second, an array of item pointers, or 'slots', grows from left to right after the header. Each slot stores the offset and size of a data cell. Third, the actual data cells (e.g., table rows) are placed at the end of the page, growing from right to left. The space between the end of the slot array and the start of the cell data is the contiguous free space.

When to use it

This structure is fundamental for database storage engines like PostgreSQL that need to manage variable-sized records within fixed-size pages. It allows for efficient insertions, updates, and deletions because data doesn't need to be constantly repacked. This provides pointer stability, which is critical for indexes that refer to records by their page and slot number.

When not to use it

If all records are a fixed, known size, a simpler array-based layout can be more efficient, as a record's location can be calculated directly from its index without the indirection of a pointer array. It also adds slight overhead for the pointers, which may be unnecessary for simple, append-only data where records are never updated or deleted in place.

One canonical example

A PostgreSQL table page uses a slotted page structure. When you insert a new row, PostgreSQL finds a page with enough free space. It writes the row data into the page from the end and adds an item pointer to the slot array near the beginning. An index on that table stores a reference to the page and the slot number, not a direct byte offset. This allows the database to perform maintenance like compaction within the page without breaking the index pointers.