Inside a Database I — Storage & Indexes

Pages: how rows physically live on disk

Start with the simplest possible mental model. A table is just a file on disk. Postgres literally stores each table as one or more files in its data directory; when you ran INSERT in Course 2, bytes were appended to a real file. This file is called a heap — "heap" because, by default, rows go in wherever there's room, in no particular order.

But the database doesn't read or write that file one row at a time, and it doesn't read it one byte at a time either. It works in fixed-size chunks called pages (sometimes "blocks"). In Postgres a page is 8 KB. Every read from disk and every write to disk moves whole pages, never half a page. A page is the database's atom of I/O.

A heap file, then, is just an array of these fixed-size pages, and each page is a little container packed with rows:

Each page has a small header, a slot array of little pointers, and the rows themselves. The rows pack in from the bottom and the pointers grow from the top until they meet in the middle — at which point the page is full and the next row goes on a new page. The pointer indirection is a neat trick: a row can be addressed as "page 2, slot 5," and if the row later has to move within the page, only the slot pointer changes, not its address.

Hold onto one consequence of this: the cost of a query is dominated by how many pages it has to read, not how many rows. If a thousand matching rows happen to sit on three pages, that's three reads. If a thousand rows are scattered one-per-page across a huge table, that's a thousand reads. This single idea explains almost everything that follows.

The problem indexes solve

Suppose orders has 50 million rows spread over a few hundred thousand pages, and you ask:

SELECT * FROM orders WHERE order_id = 998877;

How does the database find that one row? With only a heap, it has no idea where row 998877 is — remember, the heap has no order. So it does the only thing it can: it reads every page, checking every row, until it finds a match (or reaches the end). This is a full table scan, and its cost grows linearly with the table size — in the Big-O terms from Chapter 02, it's O(n). For 50 million rows, that's tens of thousands of page reads to fetch a single record. Painful.

An index is an auxiliary data structure, stored alongside the table, that keeps some column (or columns) sorted and maps each value to the location of its row — typically a "page N, slot M" pointer. Because it's kept sorted, the database can search it the way you'd search a sorted phone book: jump to the middle, decide left or right, repeat. That's a logarithmic search, O(log n) — for 50 million rows, roughly 26 steps instead of 50 million. Once the index hands back the row's location, the database reads exactly that one heap page. Two structures, working together: the index to locate, the heap to store.

B-tree indexes, deeply

"Keep it sorted and binary-search it" is the idea; the structure that actually delivers it is the B-tree — the default index type in Postgres, DuckDB, MySQL, SQLite, and essentially every relational database. It builds directly on the trees you met in Chapter 02, with one crucial twist for disk.

A B-tree is a balanced search tree: values are sorted left-to-right, and every leaf is the same distance from the root, so no lookup is ever much longer than another. You search it like a binary search tree — at each node, compare your value and follow the right child pointer down — until you reach a leaf, which holds the pointer into the heap.

Two properties make this the workhorse of databases:

• O(log n) point lookups. Each level you descend narrows the search; the depth of a balanced tree over n values is logarithmic. Find any one value in a handful of steps regardless of table size.
• Efficient range scans. Because the leaves hold values in sorted order and are chained together in a linked list, a query like WHERE order_id BETWEEN 40 AND 60 descends once to find 40, then simply walks the leaves rightward until it passes 60. ORDER BY and </>/BETWEEN all benefit. A hash index could do point lookups but not this — which is why B-trees are the default.

Indexes aren't free

If indexes make reads so fast, why not index every column? Because an index is a real, separate structure that has to be stored and, more importantly, kept in sync. Every time you INSERT, UPDATE, or DELETE a row, the database must update not just the heap but every index on that table — finding the right leaf in each B-tree and inserting the new key in sorted position. Five indexes mean five extra structures to maintain on every single write.

So indexing is a trade: you spend storage and write speed to buy read speed. The practical rule of thumb: index the columns you frequently filter on (WHERE), join on, or sort by — especially in big tables — and don't index columns you only ever read back, or tables so small a scan is already instant. A write-heavy logging table wants few indexes; a read-heavy reporting table can afford more.

Two refinements you'll meet again:

• Composite index — an index on several columns together, e.g. (customer_id, order_date). It's sorted by the first column, then the second within that. Great for WHERE customer_id = 7 ORDER BY order_date; the column order matters, because it can't efficiently use the second column alone.
• Covering index — one that includes every column a query needs, so the database can answer entirely from the index without ever touching the heap (an "index-only scan"). Saves the second lookup.

Row-oriented vs columnar storage

So far we've assumed a row lives contiguously inside a page — all of order 998877's fields (id, customer, date, amount) sitting together. That's row-oriented storage, and it's what Postgres uses. But it's not the only way to lay bytes on disk, and the alternative is the single biggest reason DuckDB and Postgres feel so different on big analytical queries.

Same logical table, two physical layouts. The difference decides which queries are cheap:

Now the payoff. Consider SELECT SUM(amount) FROM orders over a billion rows. In a row store, amount is a tiny slice of each record, but the fields are interleaved — to read every amount the database must drag every full row's worth of pages off disk, hauling along the customer, date, and everything else it doesn't need. In a columnar store, every amount sits in one contiguous run; the engine reads that column and nothing else, touching a fraction of the bytes. And because a column holds one data type with similar, often repetitive values, it compresses beautifully (a column of mostly-equal amounts shrinks dramatically), so there are fewer bytes to read in the first place. That's why DuckDB can sum a billion-row column in a heartbeat.

The flip side is just as real: to fetch one whole record, a row store grabs it from a single spot, while a columnar store must reassemble it from many separate column files. This is the heart of the Course 2 pairing — Postgres for OLTP (transactional apps: read and write individual rows constantly) and DuckDB for OLAP (analytics: scan and aggregate huge columns). Neither is "better"; they make opposite bets about which queries you'll run. We'll see this same columnar layout again on disk in Chapter 07 when we meet Parquet.

Hands-on: watch an index change things

Let's make it concrete in Postgres from Course 2. (DuckDB works too — it accepts the same SQL.) Open psql and run these in order. We'll build a table with a million rows, query it, add an index, and ask the planner what it did.

-- 1. a table with a million rows; no index yet (just the heap)
CREATE TABLE demo_orders AS
SELECT g AS order_id,
       (g % 1000)        AS customer_id,
       (random() * 500)::int AS amount
FROM generate_series(1, 1000000) AS g;

-- 2. find one row. With no index this is a FULL TABLE SCAN.
EXPLAIN ANALYZE
SELECT * FROM demo_orders WHERE order_id = 998877;

-- 3. now build a B-tree index on the column we filter by
CREATE INDEX idx_demo_order_id ON demo_orders (order_id);

-- 4. ask the exact same question again
EXPLAIN ANALYZE
SELECT * FROM demo_orders WHERE order_id = 998877;

One more thing to notice: building the index in step 3 took real time and real disk space — that's the write-side cost from the trade-off table, paid up front so every future read is cheap. Clean up with DROP TABLE demo_orders; when you're done.

✓ Check yourself

• Why is a page (block) the unit of disk I/O, and why does query cost track pages read more than rows matched?
• In one sentence: how does an index turn an O(n) scan into an O(log n) lookup?
• Why do databases use B-trees with high fan-out instead of plain binary trees?
• Name the trade an index makes — what does it buy, and what does it cost?

Next

You know where rows live and how indexes find them fast — next we'll watch the database plan a query against those structures and keep your data correct under concurrent writes. → Inside a Database — Queries & Transactions