postgres://internals

B-tree Indexes

// the problem

You have ten million rows. Postgres finds one of them in well under a millisecond — without reading them all. The answer is a balanced tree of pointers called a B-tree. First build one by hand below; then watch a real Postgres planner switch to using one, live in your browser.

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

fig.01 · b-treeorder 4 · max 3 keys/node

Key to insert

Key to find

keys

nodes

height

reads

—

result

—

readout

insert keys → watch nodes split · search a key → trace the descent

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?

A binary tree branches two ways per node, so it gets tall fast. A B-tree packs many keys per node and branches many ways, so it stays short and wide. Short matters because each level is potentially a separate page read — and in Postgres each node is an 8 KB page (the same pages from the Storage lesson). Fewer levels means fewer page reads. A B-tree holding hundreds of keys per page reaches millions of rows in 3–4 levels.

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:

sql · live postgresrun me first

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;

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;

⌘/ctrl + enter

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

sql · live postgresno index yet → Seq Scan

EXPLAIN SELECT * FROM users WHERE id = 42;

EXPLAIN SELECT * FROM users WHERE id = 42;

⌘/ctrl + enter

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:

sql · live postgresadd the index, then re-explain

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

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

⌘/ctrl + enter

The plan flips to an Index Scan with a cost of ~8 — a hundredfold cheaper. That's the B-tree descent you built above, happening for real.

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:

sql · live postgresthree predicates, three different plans

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

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

⌘/ctrl + enter

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.

// why it matters · why a bitmap scan in the middle

For a few rows, jumping around the heap via the index is cheapest. For a big fraction of the table, reading it sequentially wins. The bitmap scan is the in-between: use the index to find which pages have matches, then read those pages in order — fewer random I/Os than a plain index scan, less waste than a full seq scan.

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

sql · live postgreseditable — run it

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

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

⌘/ctrl + enter

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:

sql · live postgreseditable — run it

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

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

⌘/ctrl + enter

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:

sql · live postgresselecting only the indexed column

EXPLAIN SELECT id FROM users WHERE id = 42;

EXPLAIN SELECT id FROM users WHERE id = 42;

⌘/ctrl + enter

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) is sorted by country first, then id within each country. That makes it great for WHERE country = 'US' AND id < 100, and for WHERE country = 'US' — but not for WHERE id = 100 alone, because id is only ordered within a country. This is the leftmost-prefix rule.

// note · order the columns by how you query

Put equality columns first and the most selective columns early. One well-ordered composite index often replaces several single-column ones.

Indexes aren't free

Every index is a second structure Postgres must keep in sync. Each INSERT/ UPDATE/DELETE also writes to every affected index (write amplification), and indexes bloat and need maintenance just like tables.

// gotcha · HOT updates dodge index writes

If an UPDATE changes no indexed column and the new tuple fits on the same page, Postgres does a Heap-Only Tuple (HOT) update: it chains the new version on the page and skips touching the indexes entirely. It's a major reason to keep frequently-updated columns out of indexes and to leave some room per page (fillfactor).

Beyond B-tree

// note · the right index for the data

B-tree is the default and handles equality and range on ordered types. Postgres also ships Hash (equality only), GIN (multi-value columns: arrays, jsonb, full-text), GiST (geometric / nearest-neighbour), SP-GiST, and BRIN (huge, naturally-ordered tables — tiny indexes that store per-block ranges). Same CREATE INDEX, different USING method.

Your turn

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

// challengewrite it yourself

Make a lookup of a single user by id use an Index Scan. Create whatever index you need, then prove it with EXPLAIN.

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

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

⌘/ctrl + enter

// challengewrite it yourself

How many users are in country 'US'? Return a single count.

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

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

⌘/ctrl + enter

// what you now understand

01A B-tree keeps sorted keys in short, wide, balanced nodes; lookups descend one page per level — logarithmic, not linear.
02Each index leaf stores (key, ctid) pairs; the descent ends at a ctid, then one heap page read fetches the row.
03The planner is cost-based: a tiny result → Index Scan, a medium slice → Bitmap Heap Scan, no useful index → Seq Scan.
04An Index Only Scan answers from the index alone, helped by the visibility map.
05Composite indexes are ordered left-to-right (leftmost-prefix rule), so column order must match your queries.
06Indexes cost write amplification and maintenance; HOT updates and fillfactor mitigate it.
07B-tree is the default; GIN/GiST/BRIN/Hash exist for other data shapes.

// self-test

A B-tree is 3 levels deep. Roughly how many node reads to find one key?

// self-test

There's an index on country, but `WHERE country = 'US'` matches ~25% of rows. What is the planner most likely to do?

// go deeper

Indexes (official docs) — types, multicolumn, index-only, INCLUDE
B-Tree internals — implementation, deduplication, operator classes
Using EXPLAIN — reading plans, costs, ANALYZE/BUFFERS
nbtree README — the real Lehman & Yao B-tree in the source

nextQuery Planner