Build a Database from Zero (Part 13): The Whole Machine — and the Answer to "No Primary Key?"

Database

PostgreSQL

Build from Zero

2 hours ago1162 words·6 min read

What You'll Get Out of This

Glue together everything you've built into one honest, minimal database — rows in pages, page on disk, index by B+ tree, cached in a buffer pool;
See the two storage philosophies you've touched (heap vs index-organized) side by side;
Finally answer, with the machine in your hands, the very first question you asked me way back: why can PostgreSQL have no primary key?

Before We Start

You've built it all, piece by piece, over twelve parts. This one just wires them up and looks at the big picture.
Keep the four layers in mind: disk → page → index → buffer pool.

Step 1: The Layered Machine You've Built

Take a step back. Over twelve parts you assembled a stack, each layer solving the problem the layer above created:

txt

┌──────────────────────────────────────────────────────────┐
│  QUERY   (Part 5)          you say "what," not "how"       │
├──────────────────────────────────────────────────────────┤
│  INDEX   (Part 6-9)   hash for equality, B+ tree for range│
│                        index stores TID, not the row       │
├──────────────────────────────────────────────────────────┤
│  PAGE    (Part 10-11)  read/write by page, directory inside│
│                        TID = (page, slot)                 │
├──────────────────────────────────────────────────────────┤
│  DISK + BUFFER (Part 10,12)  pages on disk, cached in memory │
└──────────────────────────────────────────────────────────┘

Now glue them into a single object. We'll keep it deliberately small but honest — every piece is the one you wrote:

class MiniDatabase {
  constructor(file) {
    this.file = file;
    this.pages = new Map();          // pageId → page (the heap)
    this.byId  = new BPlusTree();    // id → TID (the index)
    this.pool  = new LruPool(16);    // the buffer pool
  }

  insert(row) {
    const page = this.getOrCreatePage(row);
    const slot = appendRow(page, encode(row));
    const tid = { page: page.header.pageId, slot };
    this.byId.insert(row.id, tid);        // index points at the address
  }

  findById(id) {
    const tid = this.byId.search(id);     // 1. walk the B+ tree
    const page = this.pool.getPage(this.file, tid.page); // 2. cache-aware read
    const bytes = readRow(page, tid.slot);                // 3. inside the page
    return decode(bytes);
  }
}

Read findById slowly, because it's the whole adventure in one line: index → TID → buffer pool → page → directory → row. Each step is a concept you built yourself.

Step 2: The Two Storage Philosophies, Side by Side

Your MiniDatabase above is a heap table: rows live in pages (the heap), and the index points at TIDs. But Part 9 showed you there's a different choice: sort the rows inside the index itself.

txt

HEAP TABLE (what you built, like PostgreSQL):
  index: id 42 → TID {page, slot}        jump to a page via the index
  heap:  rows in pages, unsorted          the actual data lives here

INDEX-ORGANIZED (like MySQL InnoDB):
  index (primary): the leaf IS the row    data sorted inside the index
  no separate heap                        the index IS the table

Observe what that tiny difference forces:

Heap table: rows don't need an order → you can have no primary key; the heap just accepts insertions.
Index-organized: the primary key IS the physical order → a primary key is mandatory; without one, InnoDB silently creates a hidden DB_ROW_ID.

Step 3: Answering "Why Can PostgreSQL Have No Primary Key?"

Now you can answer it with engineering, not memorization:

PostgreSQL's rows live in a heap and are only reached by an index, never arranged by one. An index is a map; the heap is the territory. If you remove the index (and its uniqueness constraint), the territory is untouched — rows stay in place, insertion order preserved. So PostgreSQL happily stores a table with no primary key.

InnoDB uses an index-organized table — the rowsaresorted inside the primary-key index. The primary key is not an add-on; it's the physical layout. So a primary key is mandatory — and if you don't give one, InnoDB fabricates a hidden one just to have a layout.

In short: PostgreSQL can have no primary key because its storage engine doesn't need one to arrange data; InnoDB does. You didn't memorize that — you derived it, from building the machine.

And the practical upside falls out too: because InnoDB sorts by the primary key, a random or ever-changing key makes inserts expensive (rows must shuffle → page splits). PostgreSQL is immune — the heap doesn't care what your key is.

Step 4: What This Means About "Real" Databases, Real Quick

You've built a toy, but every big name you've met — PostgreSQL, MySQL, even ClickHouse — is just this machine scaled up and hardened:

PostgreSQL = heap table + B+ tree index + buffer pool + WAL, plus the concurrency magic (MVCC) we'll glimpse later. Its default 8KB page and shared_buffers are exactly our PAGE_SIZE and LruPool.
MySQL InnoDB = index-organized table + B+ tree + buffer pool + WAL. Its 16KB page and Buffer Pool are the same ideas, tuned differently.

You've been building the skeleton of every real database from the ground up.

Hands-On Practice

Run findById end-to-end: build the MiniDatabase, insert a few rows, then findById(2), and log each hop — index hit, buffer hit, page directory, row decode. See the whole chain fire.
Add a second index: index by title too, so findByTitle(key) walks its own B+ tree to a TID. Notice the heap is shared — indexes are just maps over the same rows.
Prove "no primary key works": make a heap table, insert rows without any index, and Seq Scan them. Confirm it stores and retrieves — just without fast keyed lookup.

Summary and Keywords

Everything you built is one machine: disk → page → index → buffer pool → row, each layer solving the problem above it;
A heap table (PostgreSQL) stores rows unordered and an index points at TIDs → no primary key needed;
An index-organized table (InnoDB) sorts rows inside the index → a primary key is mandatory (or fabricated);
The index is a map, the heap is the territory — that's the whole reason for the difference;
You derived, not memorized: the answer to "why can PostgreSQL have no primary key?" is a storage-engine answer.

Keywords: storage engine、heap table、index-organized table、primary key、B+ tree、TID、buffer pool、page、from zero

Where to Go Next (This Series Wraps Up)

Congratulations — you built a database. Not a million-line production system, but the actual skeleton of one. Every real database you'll ever touch is this machine, scaled and hardened.

You now understand, by construction, the things most people only memorize: why Seq Scan is expensive, why the second query is faster, why indexes make lookups jump, and why tables can or can't go without a primary key.

That's the end of this series. If you want a refresher on the whole path, or to see how all the parts fit together again, head back to the series guide: