Slotted Page Design for Fixed and Variable Records

Hello! Welcome to the third lesson in our course on database systems.

In the last two lessons, we established the "big picture." We saw the layered architecture of a DBMS and, crucially, understood that the entire design is dominated by the need to manage the massive performance gap between main memory and disk. We learned that to minimize costly disk I/O, databases read and write data in fixed-size blocks.

Today, we're going to zoom in and look at what goes inside one of these blocks. The learning outcome for this lesson is to design a page layout for storing fixed-length and variable-length records. We will focus on a widely used and effective design called slotted pages. This is our first step in building the storage layer from the ground up.

From Files to Pages

At the lowest level, a database is just a collection of files on disk. The database management system takes control of these files, carving them into fixed-size chunks called pages (or blocks). A typical page size is 4KB, 8KB, or 16KB. The page is the fundamental unit of I/O; whenever the DBMS needs to read data from disk, it reads one or more entire pages into memory.

To get a clear mental model of this, let's watch a short clip.

#03 - Database Storage: Files, Pages, Tuples (CMU Intro to Database Systems)

This segment from a CMU Database Systems lecture illustrates how a database file is divided into pages and how the system manages moving these pages between disk and memory.

Please watch from 16:52 to 20:43. Focus on the visualization of the database file, the fixed-size pages, and the role of the in-memory buffer pool.

Now that we have a page, the central question is: how do we organize our records (also called tuples) inside it?

A Simple Approach and Its Flaws

The most straightforward idea is to just pack records one after another from the beginning of the page, leaving the rest as free space.

This seems simple enough, but it runs into serious problems, especially when we consider variable-length records (e.g., with VARCHAR fields) and deletions:

Deletions: If we delete RECORD 2, we are left with a "hole" in the middle of the page. To reclaim this space, we would have to shift RECORD 3 and all subsequent records, which is an expensive operation.
External Pointers: If an index (which we'll cover later) points to the exact byte offset of a record, shifting the data invalidates all such pointers. This is a major issue.
Variable-Length Records: If records have different sizes, finding the start of the Nth record requires scanning from the beginning and parsing each preceding record to find its length.

Given your background in C/C++, you can imagine the complexities of managing such a memory layout. We need a more robust solution that decouples a record's logical position from its physical location within the page.

The Solution: Slotted Pages

The industry-standard solution to these problems is a page layout called slotted pages. This design is clever, efficient, and used by major databases like PostgreSQL.

The core idea is to introduce a level of indirection. Instead of pointing directly to a record's byte offset, we point to a "slot" that then tells us where the record is.

A slotted page is typically divided into three main parts:

Page Header: Contains metadata about the page, like the number of records, the start of free space, etc.
Slot Array: A list of fixed-size entries that grows from the beginning of the page (after the header). Each entry points to a specific record in the data area.
Data Area: Contains the actual record data. This area grows backwards from the end of the page.

The space between the end of the slot array and the start of the data area is the contiguous Free Space.

Slotted Page Layout: Structure, Growth, Deletion, and Compaction — This diagram illustrates the structure of a slotted page. The slot array grows from the left, and the tuple data grows from the right. This design gracefully handles insertions, deletions, and data of variable length.

This design elegantly solves the problems of the naive approach:

Variable-Length Records: Handled naturally. The slot can store both the offset and the length of the record.
Deletions: A record is deleted by simply nullifying its entry in the slot array. This leaves the data in place but makes the slot available. The space can be reclaimed later through compaction.
Stable Pointers: An index can now use a stable Record ID (RID), typically (page_id, slot_number), to identify a record. The record data can be moved within the page during compaction, and only the small offset in the slot array needs to be updated. The external RID remains valid.

Let's watch a concise explanation of this mechanism.

#03 - Database Storage: Files, Pages, Tuples (CMU Intro to Database Systems)

This clip from the same CMU lecture provides a clear walkthrough of the slotted page architecture and its benefits.

Watch from 45:48 to 49:30. Pay close attention to how the slot array and data area grow towards each other and how this indirection solves the update problem.

Grounding It in Code

To make this concrete, let's look at a blog post that walks through a C implementation of slotted pages. Given your programming experience, this will provide a practical, systems-level view of the concepts.

Slotted Pages - Data Structures for Databases

This technical blog post, 'Slotted Pages - Data Structures for Databases', provides code examples that demonstrate how to implement and manage a slotted page layout.

Read the article from the beginning down to the end of the compact function code block. Pay special attention to the PageHeader struct, the add_cell function, and how deletion and compaction are handled. This will connect the high-level concept to a tangible implementation.

As a final reinforcement, you can see this exact pattern in real-world systems. Another blog post, "Slotted Pages: The Backbone of PostgreSQL's Data Storage", describes how PostgreSQL uses this layout. Its PageHeaderData contains pd_lower and pd_upper fields, which are the offsets that track the boundary between the slot array, free space, and the data area—exactly as described in the resources.

Test your understanding!

An index on a table needs to point to specific records. If we used the naive "append-only" page layout, what would the index have to store to locate a record? Why is the (page_id, slot_number) pair used by a slotted page system a more robust solution, particularly when a page is compacted after deletions?

Show answer

With a naive layout, the index would have to store the (page_id, byte_offset) to locate a record. The problem is that the byte_offset is unstable. If a record before it is deleted and the page is compacted by shifting data, the byte_offset of our target record changes, and the index pointer becomes invalid.

The (page_id, slot_number) pair is more robust because it provides a level of indirection. The slot_number is a stable, logical identifier within the page. When compaction occurs and the record's data is moved to a new physical byte_offset, the system only needs to update the pointer within that specific slot. The external reference from the index, (page_id, slot_number), remains completely valid.

Advanced Topics: Tuple Guts and Overflow

We've designed the page, but what about the data itself? There are two important details to consider.

1. Data Alignment Inside a Tuple

Just as we structure data within a page, we must also structure the bytes within a tuple. A tuple is essentially a byte array, and the DBMS interprets it based on the table's schema. Since you're familiar with low-level programming, you know that CPU performance can be sensitive to data alignment. Accessing a 64-bit integer that spans two 64-bit memory words can be inefficient or even cause errors on some architectures.

Database systems solve this with padding or by reordering columns to ensure that data types are aligned on word boundaries.

2. Handling Large Values with Overflow Pages

What happens if a single record is too large to fit in a page? For example, a row with a large JSON document, a TEXT field, or a BLOB containing an image could easily exceed an 8KB page limit.

The system handles this using overflow pages. The main part of the tuple is stored in the slotted page, but the oversized attribute is moved to one or more separate pages. The original tuple then just stores a pointer to the first overflow page. PostgreSQL's implementation of this is called TOAST (The Oversized-Attribute Storage Technique).

The following video discusses both alignment and overflow pages.

F2023 #04 - Database Storage Part 2 (CMU Intro to Database Systems)

This clip from another CMU lecture delves into the internal structure of tuples, including data alignment, and explains how systems handle oversized attributes with overflow pages.

First, watch the segment on data alignment from 45:38 to 55:01. This will resonate with your C++ knowledge. Then, watch the section on overflow pages from 1:10:02 to 1:16:15 to understand how large values are managed.

Conclusion

In this lesson, we moved from the abstract concept of a "block of data" to a concrete, engineered page layout. The slotted page design is a fundamental data structure in nearly all row-oriented database systems.

Key Takeaways:

Data on disk is organized into fixed-size pages, which are the unit of I/O.
The slotted page layout is an efficient design for storing variable-length records within a page.
It uses a header, a slot array growing from the start, and a data area growing from the end.
The key benefit is indirection: stable Record IDs (page_id, slot_id) allow data to be moved within a page (compacted) without invalidating external pointers from indexes.
Large attributes that don't fit on a single page are stored in overflow pages.

Preview of the Next Lesson:

We now have a design for a single page. The next logical step is to organize a collection of pages to store an entire table. In the next lesson, we will implement a heap file structure, which is an unordered collection of data pages that supports record insertion and full table scans.

Recommended resources