B-tree Indexes

Insert a few keys. Each node holds up to three keys. When a fourth would arrive, the node is full — so it splits: the middle key moves up to the parent and the node becomes two. Splitting is what keeps the tree balanced, so every leaf stays the same distance from the root. (This is bottom-up splitting — the node splits only when it actually overflows, exactly as Postgres does it.)

Now switch to search. Type a key and watch the lookup descend: at each node Postgres compares your key against the node's keys and follows a single pointer down. A tree only three or four levels tall can index millions of rows — so a search touches a handful of nodes instead of scanning the whole table. That gap is the entire reason indexes exist: a B-tree turns a linear scan into a logarithmic descent.

Why "B-tree" and not a binary tree? (do the math)

A binary tree branches two ways per node, so its height is log₂(N). For 10 million rows that's ~24 levels — and since each node could be a separate page, that's up to 24 random page reads to find one row.

A Postgres B-tree node is one 8 KB page (the same pages from the Storage lesson), and a leaf entry — a (key, ctid) pair — is only ~16 bytes. So a single page holds hundreds of keys and the tree branches hundreds of ways per level. The height is log₍fanout₎(N): with a fanout of ~500, ten million rows fit in log₅₀₀(10,000,000) ≈ 3 levels. That's the whole game — the same lookup, 24 page reads vs 3, purely because the tree is short and wide instead of tall and thin. (You'll measure a real index's size and depth a few cells down.)

From the toy to a real index

Let's leave the simulation and use an actual Postgres. This creates a 50,000-row table with no index yet:

DROP TABLE IF EXISTS users;
CREATE TABLE users (id int, email text, country text);
INSERT INTO users
SELECT g, 'user_' || g || '@example.com',
     (ARRAY['US','GB','DE','FR'])[1 + (g % 4)]
FROM generate_series(1, 50000) AS g;
ANALYZE users;
SELECT count(*) FROM users;

Ask the planner how it would find one row. EXPLAIN shows the plan without running it — read the cost and the scan type:

EXPLAIN SELECT * FROM users WHERE id = 42;

A Seq Scan: Postgres reads every page of the table (cost ≈ 944) because it has no faster option. Now give it one and ask again:

CREATE INDEX IF NOT EXISTS users_id_idx ON users (id);
ANALYZE users;
EXPLAIN SELECT * FROM users WHERE id = 42;

The plan flips to an Index Scan with a cost of ~8 — a hundredfold cheaper. Those cost numbers aren't arbitrary: the Seq Scan's ~944 is roughly read all ~368 heap pages + evaluate the filter on all 50,000 rows; the Index Scan's ~8 is descend a two-level tree + fetch one heap page. Add BUFFERS to see the descent in physical terms — one row out of 50,000 in a handful of page touches:

EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM users WHERE id = 42;

The Buffers: shared hit=… read=… line adds up to just a few 8 KB pages — the root, a leaf, and the one heap page holding the row. Now measure the index itself: over 50,000 rows it's only ~140 pages (a root plus a layer of leaves — two levels), and about a third the size of the table it indexes:

SELECT pg_relation_size('users_id_idx')       AS index_bytes,  -- ~1.1 MB
     pg_relation_size('users_id_idx') / 8192 AS index_pages,  -- ~140
     pg_relation_size('users')             AS heap_bytes;

The planner picks the cheapest path — not always the index

An index isn't always the right tool, and Postgres decides by estimated cost, not by whether an index merely exists. Add an index on country and compare three queries:

CREATE INDEX IF NOT EXISTS users_id_idx ON users (id);
CREATE INDEX IF NOT EXISTS users_country_idx ON users (country);
ANALYZE users;
EXPLAIN SELECT * FROM users WHERE id = 42;            -- ~1 row  → Index Scan
EXPLAIN SELECT * FROM users WHERE country = 'US';     -- ~25%    → Bitmap Heap Scan
EXPLAIN SELECT * FROM users WHERE email = 'user_42@example.com'; -- no index → Seq Scan

Three predicates, three plans: a tiny result uses a plain Index Scan; a chunky ~25% slice here uses a Bitmap Heap Scan (collect matching row locations from the index into a page-ordered bitmap, then read the heap in physical order); a column with no index falls back to Seq Scan. The exact choice for a mid-range slice depends on cost settings — the planner does the arithmetic every time.

EXPLAIN only estimates. Add ANALYZE to actually run it and see real timings and buffer reads (shared hit = cache, read = from disk):

EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM users WHERE id = 42;

What's actually stored in the index?

A B-tree leaf doesn't store rows — it stores (key, ctid) pairs. The key orders the tree; the ctid is the row's address back in the heap (from the Storage lesson). A lookup descends to the leaf, reads the ctid, then fetches that one heap page. These are the exact pairs an index on id holds:

SELECT id, ctid FROM users WHERE id IN (1, 42, 50000) ORDER BY id;

Crucially, the leaf pages are chained together in key order — a doubly-linked list running along the bottom of the tree. That has two big consequences beyond point lookups:

The index is already sorted, so ordering is free. ORDER BY id doesn't need a sort step — Postgres just walks the leaf chain in order. Notice the plan has an Index … Scan and no Sort node:

EXPLAIN SELECT id FROM users ORDER BY id LIMIT 10;

Min and max are instant. The smallest key is the first leaf entry, the largest is the last — so MAX(id) is a single walk to the end of the chain (Index Only Scan Backward), not a scan of 50,000 rows:

EXPLAIN SELECT max(id) FROM users;

And a range like WHERE id BETWEEN 100 AND 110 descends once to 100, then walks the leaf chain until it passes 110 — reading a contiguous run of entries instead of the whole table.

Index-only scans

If a query needs only columns the index already contains, Postgres can answer straight from the index and skip the heap entirely — an Index Only Scan:

EXPLAIN SELECT id FROM users WHERE id = 42;

This is where the Storage lesson's visibility map pays off: the index has the key but not the row's visibility, so Postgres still must confirm the row is visible — unless the _vm fork says the whole page is all-visible, letting it skip the heap touch. Covering more columns with INCLUDE makes index-only scans possible for more queries.

Multi-column indexes read left to right

An index on (country, id) sorts by country first, then by id within each country. Picture the leaf order: all the US entries in id-order, then all the GB entries in id-order, and so on. That layout is ideal for a leftmost prefix — WHERE country = 'US', or WHERE country = 'US' AND id = 100 — where Postgres descends straight to the right spot.

But what about WHERE id = 100 alone, with no country? The matching ids are scattered — one inside each country's block — so there's no single place to descend to. Run both and compare the cost:

DROP TABLE IF EXISTS orders;
CREATE TABLE orders (country text, id int, amount int);
INSERT INTO orders
SELECT (ARRAY['US','GB','DE','FR'])[1 + (g % 4)], g, g
FROM generate_series(1, 50000) g;
CREATE INDEX orders_ci ON orders (country, id);   -- ONLY this composite index
ANALYZE orders;

EXPLAIN SELECT id FROM orders WHERE country = 'US' AND id = 100;  -- prefix  → cost ~8
EXPLAIN SELECT id FROM orders WHERE id = 100;                     -- trailing → cost ~25

Both use the index — but the trailing-column query costs ~3× more. Modern Postgres (v18) uses a skip scan: it skips through each distinct country value and does a small search for id = 100 inside each block. Clever, but it's several searches instead of one clean descent, so it's far slower than a leading prefix — and slower than a dedicated (id) index would be. The old rule of thumb ("a composite can't help a non-leading column") is really about efficiency: it can, just not well.

Indexes aren't free

An index makes reads faster by making writes slower and the database bigger — you saw the id index alone was about a third the size of the table. Every index is a second structure Postgres must keep in sync: a single INSERT into a table with three indexes is really four writes (the heap tuple plus a new entry in each index), and each of those index writes may split a page. That's write amplification — the reason "just add an index" isn't free, and why an over-indexed table can be slower to write than to read. Indexes also bloat from updates and deletes and need their own maintenance (REINDEX).

Beyond B-tree

Your turn

The users table (from the first cell) has 50,000 rows.

DROP INDEX IF EXISTS users_id_idx;
-- add your index here, then run:

EXPLAIN SELECT * FROM users WHERE id = 12345;

SELECT count(*) AS count
FROM users
WHERE country = 'US';