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 up to a few hundred thousand page reads — every page in the table — 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, MySQL, SQLite, and most other row-store relational databases. (DuckDB's own indexes are a different tree, an Adaptive Radix Tree, because its columnar storage already skips data with min-max statistics.) 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 t(g);   -- t(g): names the column, so the same SQL runs in DuckDB too

-- 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

Answer from memory before opening each one.

1. Two queries against the same large table each return 1,000 rows. One needs 3 disk reads, the other about 1,000. How is that possible, and why doesn't the database simply read the rows it wants instead of whole 8 KB pages?

   Show answer

   Query cost tracks pages read, not rows matched: in the first case the rows sit together on three pages, in the second they are scattered one per page. The page is the atom of I/O because the expensive part of a read is finding the data and starting the transfer, so 8 KB costs almost the same as one byte — the database grabs the whole page and bets you will want the neighbours. See Pages.

2. Over a billion rows, a plain binary search tree and a B-tree both find a key in logarithmic time. Roughly how many page reads does each need, and what design decision produces the gap?

   Show answer

   About 30 for the binary tree versus 3–4 for the B-tree. A B-tree node is sized to fill one page, so it holds hundreds of keys and branches hundreds of ways; that high fan-out makes the tree wide and shallow. Both are O(log n), but page reads are the expensive thing, and the B-tree is binary search re-shaped to minimise them. See B-tree indexes, deeply.

3. After step 3 of the hands-on (the index on order_id exists), you run EXPLAIN ANALYZE SELECT * FROM demo_orders WHERE customer_id = 7;. What kind of scan do you expect, how many rows come back, and what would you do if this query mattered?

   Show answer

   A sequential scan of the whole heap, returning 1,000 rows (g % 1000 = 7 for one row in every thousand of the million). The tempting assumption is "the table is indexed now, so it's fast" — but an index only helps queries that filter on the column it keeps sorted, and this one is sorted by order_id. If the query matters, create an index on customer_id and run EXPLAIN ANALYZE again to confirm the plan changed. See the hands-on and The problem indexes solve.

4. A table has a composite index on (customer_id, order_date). WHERE customer_id = 7 ORDER BY order_date is fast, but WHERE order_date = '2026-03-01' is slow. Why does the same index serve one and not the other?

   Show answer

   A composite index is sorted by the first column, then by the second within each value of the first. Customer 7's entries are contiguous and already in date order, so the first query is one descent and a short walk along the leaves. Rows for a single date are scattered across every customer's section, so the index cannot efficiently use the second column alone — column order matters. See Indexes aren't free.

5. A table takes thousands of inserts per second and is read once a night by a report that filters on customer_id. A teammate proposes indexing every column "so nothing is ever slow". What do you recommend, and what about the workload would change your answer?

   Show answer

   Keep indexes to a minimum — at most one on customer_id, and possibly none if the nightly scan is fast enough. Every INSERT, UPDATE or DELETE must update the heap and find the right leaf in every index, so each extra index taxes thousands of writes a second to speed up reads that nobody runs, and costs disk space too. The balance flips for a read-heavy reporting table with few writes, which can afford more indexes on the columns it filters, joins and sorts by; either way, confirm with EXPLAIN rather than guessing. See Indexes aren't free.

6. Impressed by how quickly DuckDB sums a billion-row column, someone suggests moving the application's order-processing tables — constant single-row reads and updates by id — from Postgres to a columnar store. What is wrong with the reasoning?

   Show answer

   Columnar is not "faster", it makes the opposite bet. It wins when a query reads one or a few columns across huge numbers of rows, because it reads only those columns and they compress well. To fetch or update one whole record it must reassemble the row from every column, whereas a row store finds all the fields together on one page — which is exactly the OLTP pattern described. The query shape decides: whole records by key favour the row store, wide aggregates favour columnar. See Row-oriented vs columnar storage.

Takeaway

• A table is a heap of fixed-size pages, 8 KB in Postgres, and every read or write moves whole pages.
• Query cost follows the number of pages touched, not rows, so a thousand matching rows on three pages are cheaper than a thousand scattered across a large table.
• Without an index a point lookup is a full scan, linear in table size. A B-tree makes it a handful of page reads and also serves range scans and ORDER BY.
• A B-tree node fills a page, so each node branches into hundreds of children and the tree stays only a few levels deep.
• Indexes cost disk space and slow every INSERT, UPDATE and DELETE, so index the columns you filter, join and sort on and measure with EXPLAIN.
• Column order in a composite index matters, and a covering index can answer a query without touching the heap.
• Row stores keep a record's fields together and suit OLTP. Column stores keep a column's values together and suit aggregates and compress well.

You know where rows live and how indexes find them. Next, how the database plans a query and keeps it correct under concurrent writes. → Inside a Database: Queries & Transactions

Further reading

• Database Page Layout — PostgreSQL documentation. The page header, item pointers and tuple layout described in the pages section.
• Indexes — PostgreSQL documentation. Index types, multicolumn indexes and index-only scans.
• B-Tree Indexes — PostgreSQL documentation. The B-tree structure as implemented in Postgres.
• Use The Index, Luke — Markus Winand. A practical guide to how indexes serve queries, with the cost of each design choice.
• C-Store: A Column-oriented DBMS — Stonebraker et al., VLDB 2005. The design paper behind the case for column stores in analytics.
• Indexes — DuckDB documentation. DuckDB's own index types, which differ from the B-tree used by row stores.