B-tree indexes, pages and what indexes cost

A lookup costs one page per level, and levels grow by hundreds; every index you add is written on every insert.

Before you read: predict

ExamHall looks attempts up by primary key: SELECT * FROM attempts WHERE id = $1. At 10,000 attempts the lookup reads 2 pages of the primary-key index, then the row's table page. The table grows to 1,000,000 attempts, and the index is rebuilt the same way.

How many index pages does the same lookup read now?

The 30-second version

A B-tree stores keys sorted in 8 kB pages. Each page holds hundreds of keys or child pointers, so every level multiplies its reach by hundreds, and a lookup reads one page per level before the row. An index serves only conditions on its stored key order. Every index taxes writes; a foreign key gets none automatically.

A lookup costs one page per level, and levels grow by hundreds; every index you add is written on every insert.

How it works

Step 1 of 15

A table and each of its indexes are separate files of 8 kB pages. Reading any row means reading the page it sits on.

In the kitchen

the sheets on the shelves, in arrival order → the table's pages (step 1)

Analogy: A herbarium's catalogue

A natural-history museum stores its pressed-plant sheets on store-room shelves in the order they arrived. A catalogue of cards, filed by Latin name, says which shelf holds each sheet.

In the herbarium	In the system
the sheets on the shelves, in arrival order	the table's pages (step 1)
drawers of cards in name order, each card naming a shelf	leaf pages (step 2)
a hall board listing where each cabinet's names start; a cabinet door listing its drawers	root and internal pages (step 3)
board, door, drawer, then the shelf	one page per level, then the row (step 4)
a hundredfold bigger collection needs one more tier of signs	growth by levels (step 5)
"continued in the next drawer" at the back of each drawer	the leaf chain (step 6)
"which sheets were collected in 1931?" in a catalogue filed by name	a condition the order cannot serve (step 8)
every new sheet needs a card in each catalogue, by name, collector and country	write cost per index (step 13)
a sheet's note corrected on its own shelf, and no catalogue files by that note: no card changes	HOT (step 14)
the collectors' register lists no sheets: retiring a collector means walking every shelf	the unindexed foreign key (step 12)

In real terms: before you add an index, name the conditions it will seek on and the writes that will pay for it.

Breaks down when: a curator remembers where things are. A person learns shortcuts; the tree reads the same path every time, one page per level.

Contrasting case: a tiny table of 50 rows on one page. An index cannot beat one page; the full read is already one page (step 10).

Examples, run for real

4.1 ExamHall: one attempt's answers

EXH-1250: loading an attempt's answers read the whole answers table. answers.attempt_id references attempts, so the team assumed it was indexed. MR !1450 adds the index.

4.1 after CREATE TABLE, the indexes are: answers.answers_pkey, attempts.attempts_access_code_key, attempts.attempts_pkey
4.1 load attempt 1234's answers (60 of 144000 rows)
  as shipped (FK, no index on attempt_id)   rows read 144000 · table scans 1, index scans 0
  MR !1450 (index on answers.attempt_id)    rows read 60 · table scans 0, index scans 1
  same 60 answers: true

CREATE TABLE indexed the primary keys and the UNIQUE column, never the foreign key (step 11). Without it, every load read all 144,000 rows, 2,400 times per ECON-201 sitting (step 12).

4.2 Ticketing: inside one index

4.2 tickets_pkey, 300,000 rows: 3 levels · root: 1 page, 3 child pointers · internal: 3 pages, ~273 child pointers each · leaves: 820 pages, ~366 keys each
  lookup id 123456: root page 290 → internal page 289 → leaf page 341 → heap page 667 · BUFFERS 4 = 3 index + 1 heap: true
  leaf 341 links left to leaf 340 and right to leaf 342

Three internal pages point to 820 leaves (step 3). One lookup reads three index pages and one table page (step 4), and each leaf links to its neighbours (step 6).

4.3 Catalog: what an insert writes

4.3 insert 10,000 orders
  1 index   (pkey)                                  index entries 10000 · index pages 30 · table pages 64
  4 indexes (created_at, customer, pkey, status)    index entries 40000 · index pages 129 · table pages 64

The same rows cost four entries each with four indexes, and the indexes outgrow the table (step 13). Deduplication is off here, so each entry is counted once.

Picture it

Concept illustration for this lesson. — An illustration to help it stick. The mechanism is in the sections above.

Try it

Answer first, then check. Nothing is saved.

Question 1 of 6

A ticketing schema is events (id PRIMARY KEY, name) and tickets (id PRIMARY KEY, event_id REFERENCES events (id), seat), created by one migration. tickets holds 50,000 rows. Deleting a cancelled event that sold no tickets reads all 50,000 ticket rows.

Which is the bug?

Question 2 of 6

A shop's database uses the collation en_US.utf8. Its search runs SELECT id, name FROM products WHERE name LIKE 'lamp-0012%'. A plain b-tree index on name exists, yet the query reads all 100,000 rows.

Which change makes it read only the matching rows?

Question 3 of 6

payments has b-tree indexes on id, status and created_at, and its pages have free room. A nightly job runs UPDATE payments SET retries = retries + 1 on 1,000 failed payments; on Monday it added no index entries. On Tuesday someone runs CREATE INDEX ON payments (retries), and the job runs again.

How many new index entries does Tuesday's job add, over all indexes?

Question 4 of 6

A festival's passes table holds 100,000 rows, spread through the table in id order: 89,500 valid, 10,000 transferred and 500 refunded. It has a b-tree index on status, and its statistics are fresh. Two queries run: WHERE status = 'valid' and WHERE status = 'refunded'.

Which of them reads the whole table in PostgreSQL 17?

Question 5 of 6

A music service's plays table holds 500,000 plays, with every time in UTC, and has a b-tree index on played_at. A report needs exactly the plays of 6 October 2026, and it should read only those rows.

Which WHERE clause should it use?

Question 6 of 6

A chat app's sessions table has b-tree indexes on id, user_id and last_seen. Each heartbeat runs UPDATE sessions SET last_seen = $2 WHERE id = $1, and each one adds an entry to all three indexes. A nightly cleanup may read the whole table.

Which change makes heartbeats add no index entries?

Go deeper

Pro tips

List foreign keys whose referencing column leads no index. Query pg_constraint (contype f) against pg_index, and index every column you join on or delete parents by. When: after any migration that adds a REFERENCES (steps 11–12).
Watch the in-place update ratio. pg_stat_user_tables has n_tup_upd and n_tup_hot_upd; a hot table whose ratio falls after a migration usually gained an index on a column it updates. When: a frequently updated table's indexes grow faster than its rows (steps 14–15). Verify: the per-transaction view of the same counters prints HOT 1000 of 1000 before an index on the updated column and HOT 0 of 1000 after it.

Source

PostgreSQL 17, B-Tree Structure (btree implementation): https://www.postgresql.org/docs/17/btree.html · fetched 2026-09-27. "PostgreSQL B-Tree indexes are multi-level tree structures, where each level of the tree can be used as a doubly-linked list of pages" (steps 3, 6); "Typically, over 99% of all pages are leaf pages" (step 3); a root page split "adds a new level to the tree structure" (step 5). Valid as of 2026-09-27.
PostgreSQL 17, Index Types: https://www.postgresql.org/docs/17/indexes-types.html · fetched 2026-09-27. B-trees handle <, <=, =, >=, >, plus BETWEEN and IN (step 7); LIKE can use one "if the pattern is a constant and is anchored to the beginning of the string", and without the C locale "you will need to create the index with a special operator class" (step 9). Valid as of 2026-09-27.
PostgreSQL 17, Indexes on Expressions: https://www.postgresql.org/docs/17/indexes-expressional.html · fetched 2026-09-27. An index column "can be a function or scalar expression computed from one or more columns" (step 8). Valid as of 2026-09-27.
PostgreSQL 17, Unique Indexes: https://www.postgresql.org/docs/17/indexes-unique.html · fetched 2026-09-27. "PostgreSQL automatically creates a unique index when a unique constraint or primary key is defined for a table" (step 11). Valid as of 2026-09-27.
PostgreSQL 17, Constraints, Foreign Keys: https://www.postgresql.org/docs/17/ddl-constraints.html · fetched 2026-09-27. A parent DELETE "will require a scan of the referencing table", and "the declaration of a foreign key constraint does not automatically create an index on the referencing columns" (steps 11–12). Valid as of 2026-09-27.
PostgreSQL 17, Heap-Only Tuples (HOT): https://www.postgresql.org/docs/17/storage-hot.html · fetched 2026-09-27. HOT needs an update that "does not modify any columns referenced by the table's indexes, not including summarizing indexes" and "sufficient free space on the page"; then "New index entries are not needed" (steps 14–15). The partial-index case (predicate columns count) is observed in D2, not quoted. Valid as of 2026-09-27.
Markus Winand, Use The Index, Luke (curriculum source): background for steps 4 and 8; not quoted.

Checked against the tools and docs as of 2026-09-27.

Predict first