Build a Database from Zero (Part 9): An Index Stores Addresses — Hello, TID

Database

PostgreSQL

Build from Zero

2 hours ago1337 words·7 min read

What You'll Get Out of This

Realize the key insight from Part 8: an index stores keys and pointers, not the data itself;
Invent the "address" of a row — the TID — and build an index that uses it;
See the two big ways to organize rows (heap vs index-organized) and why one of them needs a primary key.

Before We Start

Know Part 8: the B+ tree holds keys to steer and a leaf chain for ranges;
Know Part 4: the raw rows live "somewhere" — we called it a table, but we never gave a row an address.

The Stepping-Back Question

Part 8 left you with the B+ tree. But here's a subtle thing worth pausing on: a B+ tree does not store the rows. It stores keys, plus something that points at a row. So what exactly does it point at?

In Part 4 we stored rows in a plain array and used array indexes to find them. But a real database's rows won't be reachable by "the 5th element" — rows get added, removed, and moved. We need a stable way to name a row's location, independent of "which position it happens to be in an array."

That's what we're going to invent right now.

Step 1: Give Every Row an "Address"

Let's decide: each row gets a row address, a pair of numbers. Think of it like a book in a library: it lives in a shelf (page) at a spot (offset). We'll call this address a TID (tuple id) — a position that says "page N, slot M."

// a "row" and the address of where it lives
// address = { page, slot }
const books = [];           // the heap: rows in insertion order
const addresses = [];       // addresses[i] = { page, slot } for row i

// insert a row, and record where it landed
function insert(title, price) {
  const row = { id: books.length + 1, title, price };
  books.push(row);
  // in reality, "where it landed" is a specific page+slot on disk
  addresses.push({ page: Math.floor(books.length / 50), slot: books.length % 50 });
  return addresses[addresses.length - 1];
}

const tid = insert("Database Internals", 59);
// tid = { page: 0, slot: 0 }

Note the important shift: an address is not "the 5th row overall" — it's "page 1, slot 3." That's stable even if you add more rows, because it doesn't depend on a global position.

Step 2: The Index Points at the Address

Now build the index. Side by side with the heap (where rows are), we keep a B+ tree. But the tree's leaves store keys → TIDs, not the whole row.

// index: keys (e.g. id) → TID (address), NOT the row itself
class Index {
  constructor() {
    this.byId = new BPlusTree();      // id -> TID
  }

  add(id, tid) {
    this.byId.insert(id, tid);
  }

  // "SELECT * FROM books WHERE id = 42"
  findById(id) {
    const tid = this.byId.search(id);
    if (!tid) return null;
    return books[tid.slot];          // go to the address, fetch the row
  }
}

So a query now takes two steps:

txt

1. index.search(id=42)   → TID { page: 0, slot: 1 }      (walk the B+ tree)
2. books[slot]           → the actual row                (follow the address)

This is the crucial idea: the index points at a location, and the data lives elsewhere. The index is just a map; the rows are the payload.

Step 3: Heap vs Index-Organized — The Fork in the Road

Now that we have rows and addresses, a design choice appears: should the index store the address, or should the row be sorted inside the index itself?

There are exactly two answers, and they're the two philosophies of real databases:

Option A: Heap table. Rows live in a "heap" in insertion order. The index stores a pointer/TID to each row. (This is PostgreSQL.)

txt

index:  id 42 → { page:3, slot:2 }        ← pointer into the heap
heap:   [row][row][row][row][row]...       ← data in insertion order

Option B: Index-organized table. The rows ARE the index — sorted inside the leaf itself, no separate heap. The "address" isn't needed elsewhere because the data lives at the leaf. (This is MySQL InnoDB.)

txt

index (primary):
  leaf: ...→ [ id:10, whole row ] → [ id:20, whole row ] → ...
                     ↑ the row is right here, no pointer needed

Notice what Option B forces: because the primary key physically arranges the whole table, InnoDB must have a primary key — otherwise it has no way to order the rows, so it silently creates a hidden one. PostgreSQL can render rows without a primary key, because it never stores them by key.

And now you can finally see the answer to the question from way back — "why can PostgreSQL have no primary key?" Because its rows live in a heap and are only reached by an index, never arranged by one. The index is optional; the heap isn't.

Step 4: Why This Distinction Matters — "Return to the Table"

Here's the practical consequence, and it explains a term you might have heard: "returning to the table."

In a heap table (PostgreSQL), after an index finds the TID, you must follow the pointer back to the heap to grab the actual row the query didn't include in the index. That's a second hop — useful, but a cost.

If the index already contains everything the query needs (the columns the query asks for are inside the leaf), you skip the second hop — no need to go back to the heap. That's what you might know as a covered index / Index Only Scan.

In an index-organized table (InnoDB), the primary index is the row, so a primary-key lookup never needs to "go back" — it's already there. That's a big part of why InnoDB sometimes feels faster for keyed lookups.

txt

heap table (PG):
  index(id=42) → TID → go to heap for the rest of the row   (2 hops)

index-organized (InnoDB):
  index(id=42) → leaf already has the whole row              (1 hop)

Hands-On Practice

Build the two-hop lookup: using your books array + a B+ tree mapping id → slot, implement findById that first searches the index, then goes to the array.
Simulate the "no primary key" case: make a heap table with no index at all, and a users table with no primary key. Confirm you can still insert and scan — just without fast keyed lookup.
Show the covered-index win: create an index that stores both id and title in the leaf; then a query for ("id", "title") won't need the heap. Print when the heap hop happens and when it doesn't.

Summary and Keywords

An index stores keys → addresses, not the data; a row's address is its TID (page + slot);
A keyed lookup is two hops: search the index for a TID, then follow the TID to the row;
Heap table (PostgreSQL): rows live unordered, index points at them — no primary key required;
Index-organized table (InnoDB): rows are sorted inside the index itself — a primary key is mandatory, so InnoDB invents one if you don't;
Not needing to "return to the table" is what a covered index is all about.

Keywords: TID、tuple id、pointer、heap table、index-organized table、return to table / heap lookup、covered index、Index Only Scan

What's Next

So far, that entire machine — the heap, the index, the TID — has been living in memory, just JS arrays. It's fast, but it evaporates the moment the program ends. If we want a real database, the data has to survive a restart.

That's Part 10: we take our rows and write them to a file, and load them back. Persistence is where "a toy" becomes "a database."