Lesson 10 · Indexes

Why indexes exist: the B-tree

The alternative to reading every page — and the one index you'll use 90% of the time.

Your win: explain what an index is, how a B-tree finds a row without a sequential scan, and what kinds of query it accelerates.

The problem: the sequential scan

Without a useful index, finding rows means a sequential scan — reading every page of the heap (Part 2) and checking each tuple. Fine for a small table or when you want most of it; disastrous for finding a handful of rows in millions.1

An index is a sorted side structure

An index is a separate structure that lets Postgres locate matching rows fast. The default type is the B-tree — a balanced search tree:

[ root ] ← branch nodes route the search / | \ [ · ] [ · ] [ · ] ← branch nodes / \ / \ / \ [leaf][leaf][leaf]… ← leaves: sorted keys + ctid (→ heap row) ⇄ ⇄ ⇄ doubly-linked → range scans go forward/back

Branch nodes route a lookup down to a leaf in ~O(log n) steps; leaves hold the indexed keys in sorted order as a doubly linked list, each pointing at a heap tuple's ctid.2 Because the leaves are sorted, a B-tree serves equality (=), ranges (<, >, BETWEEN), ORDER BY, and prefix LIKE 'abc%'.

Index → then heap fetch The index gives you a ctid; Postgres then does a heap fetch to read the actual row from its page (Part 2). So an index lookup is "walk the tree → fetch the row". (An index-only scan can skip the fetch — Lesson 12.)
Anchor Every primary key and unique constraint is backed by a B-tree — pk__emails on email_id. Your migrations also add explicit B-trees on resource_path (tom/1059:43) and composites like (email_id, recipient_address, recipient_type) (notificationmgmt/1026). B-tree is the workhorse.
Read this next

Use The Index, Luke! — Anatomy of an index

The clearest explanation of the B-tree (the tree + the doubly-linked leaf nodes) — the single best resource for this whole part. Then the official indexes chapter.

→ use-the-index-luke.com/sql/anatomy
→ postgresql.org/docs — Indexes

Check yourself (from memory)

Q1. Without a useful index, a query does a…

It reads every page of the heap. Fine for small/most-of-table; an index avoids it for selective queries.

Q2. The default Postgres index type is…

B-tree — balanced tree, sorted leaves. Used for ~90% of indexing needs, including every PK/unique.

Q3. A B-tree efficiently supports…

Sorted leaves → =, ranges, ORDER BY, prefix LIKE. Multi-value data needs GIN (Lesson 11).
What is an index, how does a B-tree find a row, and what does it support?
recall, then click to reveal
An index is a sorted side structure that locates rows without a sequential scan. The default B-tree is a balanced tree: branch nodes route the search to leaf nodes, which hold keys in sorted order (a doubly linked list) with pointers (ctid) to heap tuples. Lookup is ~O(log n); sorted leaves serve equality (=), ranges (</>/BETWEEN), ORDER BY, and prefix LIKE. After finding the ctid it does a heap fetch (unless index-only). Every PK/unique is a B-tree.
Want to see EXPLAIN flip from "Seq Scan" to "Index Scan" when you add one? That's Part 4 — ask me for a preview.

1. PostgreSQL — Indexes.

2. Use The Index, Luke! — Anatomy of an index.