The Storage Engine — Heap Files & Free Space

1 Heap file organization

Recall from Session 2 that the database stores data in fixed-size pages (usually 4 KB or 8 KB), and that within a page, rows live in a slotted layout. But a table like users has way more rows than fit in one page. So the database needs a way to organize many pages into one logical table. The simplest and most common way is a heap file.

A heap file is an unordered collection of pages where rows (also called tuples) are stored with no sorting and no relationship between their physical position and their values. New rows simply go wherever there's free space. The name has nothing to do with the "heap" data structure from algorithms class — here it just means "an unsorted pile."

Two ways to organize the pages

If a table is just "a set of pages," the engine still needs to find them on disk. There are two classic designs, and real systems generally use the second.

Option A — Linked list of pages

The database keeps a special header page with two pointers: one to the first page that has free space, and one to the first full page. Every data page then stores a pointer to the next page, forming a chain — like a treasure hunt where each clue points to the next.

This works, but it's clumsy. To find a page with free space you might have to walk the whole chain, following pointer after pointer — slow when a table has millions of pages.

Option B — Page directory

A smarter design keeps a page directory: special directory pages that hold an array of entries, one per data page. Each entry records the page's location (its page number) and how much free space it currently has. To find room for a new row, the engine just scans this compact directory instead of every data page.

How a full-table scan works

Because a heap is unordered, the only way to answer a query that can't use an index — say SELECT * FROM users WHERE age > 30 with no index on age — is a full-table scan (also called a sequential scan): read every page, look at every row, and keep the ones that match. It's the toy-box dump-and-look from our story.

# Full-table scan over a heap file
matches = []
for page_id in heap.all_pages():        # walk every page in the heap
    page = buffer_pool.fetch(page_id)    # load it into memory (Session 4!)
    for slot in page.slots():           # walk every slot in the page
        if slot.is_live():               # skip deleted/empty slots
            row = page.read(slot)
            if row.age > 30:             # apply the WHERE filter
                matches.append(row)
return matches

2 Free space management

Every time you INSERT a row, the engine must answer one question: which page has enough free space to hold it? Scanning every page to find out would be far too slow, so databases keep a dedicated structure that tracks free space.

The free space map

A free space map (FSM) is a compact index that records, for each page, roughly how many bytes are free. It's the "parking board." The page directory from Topic 1 is one way to implement it; PostgreSQL keeps a separate small file (the _fsm fork) shaped as a tree so it can find a page with enough room in O(log N) instead of scanning.

Finding a page to insert into

Here's the decision the storage engine makes on every insert:

# Free space map snapshot (bytes free per page)
page 0 -> 0      # full
page 1 -> 40     # almost full
page 2 -> 512
page 3 -> 7000

# INSERT a 200-byte row:
target = fsm.find_page(200)    # first page with >= 200 free
# skips page 0 (0) and page 1 (40), picks page 2 (512)
page2.insert(row)                # now ~312 bytes free
fsm.update(page=2, free=312)   # keep the map current

Fragmentation — why pages get messy

Over time, inserts, deletes, and updates leave pages with awkward gaps. There are two flavors of wasted space:

Recall the slotted-page layout from Session 2: rows are added from one end and the slot array grows from the other. When a row is deleted, its bytes become a hole. The engine can compact a page — slide the remaining rows together to merge the holes into one contiguous free region — so a new row can fit. The slot array means it can do this without breaking any external pointers (more on that in Topic 4).

3 Variable-length records & overflow

Many columns are variable-length: a VARCHAR, TEXT, JSON, or BLOB can be a few bytes or a few megabytes. From Session 2 you know a slotted page handles variable-length rows by storing, in each slot, an offset and length pointing at where the row's bytes live in the page. That's fine — until a value is too big to fit on a single page at all.

Records that grow and shrink

When you UPDATE a row and a variable-length column gets longer, the row may no longer fit in its current spot. Two things can happen:

• It still fits in the page: the engine compacts the page to make a big-enough hole and rewrites the row there, updating its slot's offset.
• It no longer fits in the page: the engine moves the row to a different page entirely and leaves a forwarding pointer behind — covered in detail in Topic 4.

When a value shrinks, the freed bytes become a hole, recovered later by compaction.

The hard case: values bigger than a page

If a single column value is larger than a page (e.g. a 2 MB document in a 8 KB page), it physically cannot live inline. Databases use overflow pages: the big value is stored on one or more extra pages, and the main row keeps only a small pointer to them.

TOAST — PostgreSQL's take

PostgreSQL calls this mechanism TOAST (The Oversized-Attribute Storage Technique). Because a Postgres row must fit within a single 8 KB page, when a row gets too big the engine springs into action on the large variable-length columns, in this order:

CREATE TABLE posts (
    id    INT,
    title VARCHAR(200),
    body  TEXT          -- could be 1 MB!
);

INSERT INTO posts VALUES
    (1, 'Hello', '... 1,000,000 chars of text ...');

4 Deletes, updates & vacuum

Logical vs physical deletion

There are two very different meanings of "delete":

• Logical deletion — mark the row as dead but leave its bytes in place. Fast, and safe for concurrent readers who might still need the old version.
• Physical deletion — actually reclaim the bytes so the space can be reused. Slower, done later.

The marker left by a logical delete is called a tombstone: a flag (often a single bit, or in MVCC systems a transaction id) that says "this row is no longer live; skip it." Look back at the scan pseudocode in Topic 1 — the slot.is_live() check is exactly what skips tombstoned rows.

Why we need vacuum / compaction

All those tombstoned, dead rows are dead tuples — bytes that are logically gone but still physically occupying pages. Left alone they cause bloat: the table grows on disk and scans get slower because they wade through dead rows. The cleanup job is called vacuum (PostgreSQL's name) or, more generally, compaction.

How an update can move a tuple

An UPDATE is conceptually a delete-plus-insert. In MVCC systems it literally writes a new version of the row and tombstones the old one. Two cases matter:

• New version fits on the same page: great — it's written nearby, old version becomes a dead tuple for vacuum to clean.
• New version doesn't fit (e.g. a column grew): the new version goes to a different page, and the old slot is replaced with a forwarding pointer (PostgreSQL: a redirect in the page's item array) that says "the current row is over there."

# Page 5, before:
slot 0 -> (id=10, name="Pen")
slot 1 -> (id=20, name="Mug")
slot 2 -> (id=42, name="Hat")        # <- we will update this

UPDATE products
   SET name = 'Wide-brim summer straw hat, limited edition'
 WHERE id = 42;

# Page 5, after:
slot 0 -> (id=10, name="Pen")
slot 1 -> (id=20, name="Mug")
slot 2 -> REDIRECT to (page 9, slot 0)   # forwarding pointer

# Page 9, after:
slot 0 -> (id=42, name="Wide-brim summer straw hat, limited edition")

★ Putting it all together

You just learned how a database turns a pile of pages into a living, breathing table. 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 3 — Storage Engine 2 — the class handout that accompanies this session.

Papers, docs & deep dives

• CMU 15-445 — Database Systems — Andy Pavlo's renowned course; the storage / heap-file / page-layout lectures are the gold-standard intro to everything in this session.
• PostgreSQL docs — TOAST — the official, authoritative description of how PostgreSQL compresses and stores oversized attributes out-of-line (Topic 3).
• PostgreSQL docs — Routine Vacuuming — explains dead tuples, bloat, VACUUM vs VACUUM FULL, and autovacuum (Topic 4).
• PostgreSQL docs — Database Page Layout — how a heap page, item pointers, and TIDs/redirects actually look on disk; ties Topic 1 and Topic 4 together.
• PostgreSQL docs — Free Space Map — the precise design of the FSM fork behind Topic 2.
• Alex Petrov — "Database Internals" — an excellent book whose storage-engine chapters cover heap files, slotted pages, and overflow in depth.