The Storage Engine — Pages & Records

1 Why databases think in pages

A database's job is to store more data than fits in memory, on a disk, and still answer questions quickly. To do that it has to understand one harsh fact of hardware: disks are slow, and they don't let you read one byte at a time. This single fact shapes the entire design of a storage engine.

The hardware reality: blocks, not bytes

Storage hardware does not hand you individual bytes. It works in fixed-size chunks:

• A spinning hard disk drive (HDD) is organised into sectors (classically 512 bytes, now often 4 KB). To read anything, the disk must physically spin the platter and move a read head to the right track — a slow, mechanical seek.
• A solid-state drive (SSD) has no moving parts, but it still reads and writes in fixed units called pages (typically 4 KB) and erases in larger blocks. You cannot rewrite a single byte in place.

So at the hardware level, the smallest amount you can usefully transfer is a block, not a byte. The numbers behind this are dramatic:

Reading from a disk is thousands to hundreds of thousands of times slower than reading from memory. And crucially, most of that cost is the setup — the seek and rotation on an HDD, or the controller round-trip on an SSD. Once the head is in place, grabbing the next few kilobytes is almost free. This is the key insight:

What is a page?

A page (sometimes called a block) is a fixed-size, contiguous region of the database file — the unit the storage engine reads from and writes to disk as a single operation. Common sizes:

• PostgreSQL: 8 KB pages (default).
• MySQL / InnoDB: 16 KB pages (default).
• SQLite: 4 KB pages (default, configurable).
• SQL Server / Oracle: 8 KB pages.

The page size is chosen to be a multiple of the operating system's and hardware's block size so that one logical page maps cleanly onto whole physical blocks — no wasted half-reads.

Why row-at-a-time disk access is too slow

Suppose a table row (a tuple) is 128 bytes. If the database fetched one row per disk read, every single row would cost a full seek — ~10 ms on an HDD. Reading a million rows would take ~10,000 seconds (almost 3 hours) just in seek time. By contrast, packing those same rows into 8 KB pages (about 60 rows per page) means ~16,000 page reads instead of a million — roughly 60× fewer disk trips.

2 The anatomy of a page

A page is just a fixed-size array of bytes — say 8,192 of them. The storage engine imposes structure on those raw bytes. Almost every page is split into two regions: a small page header and a larger data region.

The page header

The page header is a small block of metadata at the start of the page (often 20–100 bytes) that describes the page itself. It typically holds:

The header is small but mighty: without it, the engine couldn't tell where the data ends, how many records are present, or whether the page is corrupted.

The data region — where records live

The rest of the page holds the actual records (the serialized rows / tuples). The big question is: how do we lay records out, and how do we find a specific one later? The answer depends on whether records are all the same size or not.

Fixed-length vs. variable-length records

# Fixed-length layout: records packed back-to-back after the header.
record_size = 32
header_size = 24
n           = 5

offset = header_size + n * record_size   # 24 + 5*32 = 184
record = page_bytes[offset : offset + record_size]  # bytes 184..216

3 Slotted pages

The slotted page is the standard layout for variable-length records, used by PostgreSQL, SQLite, SQL Server, and most others. It solves the two problems from Topic 2 at once: it handles variable sizes, and it lets records move without breaking their addresses.

The layout: grow from both ends

A slotted page grows from both ends toward the middle:

• Right after the header sits the slot array (also called the slot directory or line pointer array). It grows downward from the top. Each slot is a small fixed-size entry — typically a (offset, length) pair — that points to one record.
• The actual record data is packed from the bottom of the page upward.
• The free space is the gap in the middle, shrinking from both sides as the page fills.

Here's the picture. The slot array grows down from the header; records grow up from the end; free space is squeezed in between:

  byte 0 ─────────────────────────────────────────────── byte 8191
┌────────────┬───────────────────────┬─────────────────┬──────────────┐
│   HEADER   │  SLOT ARRAY  ───────►  │   free space    │ ◄─── RECORDS │
│ (metadata) │  [s0][s1][s2]...       │   (the gap)     │  ...R2 R1 R0 │
└────────────┴───────────────────────┴─────────────────┴──────────────┘
   grows →       grows downward →        shrinks            ◄ grows upward

   slot s0 ─┐                                          ┌── record R0
   slot s1 ─┼──── each slot = (offset, length) ───────►├── record R1
   slot s2 ─┘        points to a record                └── record R2

Each slot is tiny and fixed-size (e.g. 4 bytes: a 2-byte offset + 2-byte length). So even though records vary in size, the slot array is a neat fixed-stride array — and that gives us back the cheap arithmetic addressing we lost in Topic 2, but at the slot level instead of the record level.

The Record ID — a stable address

A record is identified not by its byte position, but by its Record ID (RID): the pair (page number, slot number). PostgreSQL calls this the tuple ID (TID/ctid). Because the RID names a slot, not a byte offset, the engine can shuffle records around inside the page and the RID still works — it just updates the offset stored in the slot.

Insert, delete, and move — without breaking RIDs

Let's walk through the operations on a page with three records R0, R1, R2 in slots 0, 1, 2.

# Insert record R3 of length L
free_end   = header.free_space_end       # top of the record area
new_offset = free_end - L                 # carve L bytes off the free gap
page[new_offset : free_end] = R3_bytes
slots.append( (offset=new_offset, length=L) )   # this is slot 3 → RID (page, 3)
header.free_space_end = new_offset

# Delete the record in slot 1
slots[1] = (offset=0, length=0)   # tombstone: slot now points to nothing

# Compaction: rewrite live records contiguously, fix up slot offsets
write_ptr = end_of_page
for slot in slots:
    if slot.is_live():
        write_ptr -= slot.length
        move record bytes to write_ptr
        slot.offset = write_ptr          # RID (page, i) unchanged — only the offset moved
header.free_space_end = write_ptr

Updating a record to a larger size is the interesting case: if it still fits in the page's free space, the engine rewrites it (possibly moving it and updating its slot). If it no longer fits, the engine places it on another page and leaves a small forwarding pointer (a redirect) in the original slot — so the RID still works, it just hops once. PostgreSQL's HOT updates and SQL Server's forwarded records are real-world versions of this.

4 Byte-level record encoding

Inside a slot's region sits the actual record — a single row turned into a flat stream of bytes. Turning a structured row into bytes is called serialization (and turning it back is deserialization). Let's see exactly what those bytes are.

The pieces of a serialized record

A typical record is laid out as: a small record header, then the fixed-length fields, then the variable-length fields. The header usually contains:

• A null bitmap — one bit per column, set to 1 if that column is NULL. This is how the engine stores "this field has no value" without wasting space on the value itself.
• Sometimes a count of columns, a version tag, or visibility info for concurrency (we'll meet that in a later session on transactions).

Fixed-length fields are easy; variable-length need offsets

Fixed-length fields (like INT = 4 bytes, BIGINT = 8 bytes) are placed first, back-to-back, so the deserializer knows each one's position by simple arithmetic.

Variable-length fields (like VARCHAR) are the problem: their length isn't known in advance. Two common solutions:

• Length prefix: store the length right before the data (e.g. [len=5]["Medha"]). To skip to the next field, read the length, then jump that far.
• Offset array: keep an array of offsets at the start of the record, one per variable field, pointing to where each field's data begins. This gives O(1) access to any variable field without scanning earlier ones.

A concrete byte-layout example

Let's serialize one real row. Take this table and row:

CREATE TABLE users (
    id     INT,           -- 4 bytes, fixed
    age    SMALLINT,      -- 2 bytes, fixed
    name   VARCHAR,       -- variable length
    email  VARCHAR        -- variable length
);

-- The row we want to store:
INSERT INTO users VALUES (7, 30, 'Medha', NULL);

So id = 7, age = 30, name = 'Medha' (5 characters), and email = NULL. Here is one reasonable byte layout (little-endian integers, a 1-byte null bitmap, length-prefixed strings). Byte offsets are shown on the left:

offset  bytes (hex)        meaning
─────────────────────────────────────────────────────────────
  0     04                 null bitmap = 0000 0100b
                            └─ bit0 id=present, bit1 age=present,
                               bit2 name=present, bit3 email=NULL (the set bit)
─────────────── fixed-length fields ─────────────────────────
  1     07 00 00 00        id    = 7   (INT, 4 bytes, little-endian)
  5     1E 00              age   = 30  (SMALLINT, 2 bytes; 0x1E = 30)
─────────────── variable-length fields ──────────────────────
  7     05                 name length = 5  (1-byte length prefix)
  8     4D 65 64 68 61     name data   = 'M' 'e' 'd' 'h' 'a'  (ASCII)
        (email is NULL → bit 3 set in the bitmap → no bytes stored at all)
─────────────────────────────────────────────────────────────
total record size = 13 bytes

Walk through it the way the database would when reading the row back:

1. Read byte 0 → the null bitmap 0x04 = binary 00000100. Bit 3 is set, so email is NULL and will occupy zero bytes later — we skip it entirely.
2. Read 4 bytes at offset 1 → id = 7.
3. Read 2 bytes at offset 5 → age = 30.
4. Read 1 length byte at offset 7 → 5, then read 5 bytes → the string "Medha" for name.
5. email was flagged NULL by the bitmap, so there is nothing more to read. Done — 13 bytes total.

def read_user(rec):
      null_bitmap = rec[0]
      pos = 1

      # id: INT, 4 bytes, little-endian
      id = int_from_bytes(rec[pos:pos+4])   # 0x07000000 → 7
      pos += 4

      # age: SMALLINT, 2 bytes
      age = int_from_bytes(rec[pos:pos+2])  # 0x1E00 → 30
      pos += 2

      # name: length-prefixed VARCHAR
      n = rec[pos]; pos += 1             # length = 5
      name = rec[pos:pos+n].decode(); pos += n   # "Medha"

      # email: check the null bitmap (bit 3) before reading anything
      if null_bitmap & (1 << 3):
          email = None                   # NULL → no bytes consumed
      else:
          m = rec[pos]; pos += 1
          email = rec[pos:pos+m].decode()

      return (id, age, name, email)

★ Putting it all together

You just followed your data all the way down to the bits. Here's the one-paragraph story that connects all four topics:

Quick self-check

📚 References & Further Reading

Class material

• 📄 Original course notes / handout (source sheet) — open the shared class material for this session.
• DBMS Session 2 — Storage Engine (the class handout for this session).

Papers, docs & deep dives

• CMU 15-445/645 — Database Systems (course site) — the gold-standard university course; the "Database Storage" lectures cover pages, slotted pages, and tuple layout exactly as in this session, with free video lectures and slides.
• PostgreSQL Docs — Database Page Layout — the canonical, real-world reference: the page header, the line-pointer (slot) array, item layout, and the heap tuple header described byte by byte.
• Silberschatz, Korth & Sudarshan — Database System Concepts — the classic textbook; the storage and file-structure chapters formally cover fixed vs. variable-length records and slotted pages.
• PostgreSQL Docs — TOAST — what happens when a record is too big to fit on one page: oversized variable-length fields are compressed and moved out-of-line, a real-world extension of Topic 4.
• MySQL Docs — InnoDB Row Formats — how a different production engine encodes records (COMPACT/DYNAMIC formats, null bitmaps, hidden columns), great for comparing against PostgreSQL.
• Alex Petrov — Database Internals — a modern, approachable book whose first chapters walk through page structure, slotted pages, and record encoding in depth.