BrevFeed
Sign in

41. B-tree indexes

📖 Reading · 10 min
💡 Most code boxes below are live — edit one and hit Run. Boxes without a Run button are reference-only (they need a real Postgres server).

What an index actually is

An index is a separate data structure, stored alongside a table, that lets the engine find matching rows without reading every row in the table — the difference between a Seq Scan (previous lesson) and an Index Scan. Postgres's default, general-purpose index type is the B-tree (balanced tree) — a sorted, hierarchical structure that supports fast equality lookups, range queries, and sorted retrieval, all with O(log n) search cost instead of O(n).

(The full internal structure — nodes, pages, how the tree balances itself as it grows — is genuinely visual and worth looking up if you're curious, but beyond this course's scope. This lesson focuses on using B-tree indexes correctly; conceptually, think of it like a phone book's alphabetical sorting: you don't scan every name to find "Smith," you jump to the right section directly.)

Creating one, and seeing the plan change

-- Without an index, filtering on email requires a full scan.
EXPLAIN ANALYZE SELECT * FROM customer WHERE email = 'MARY.SMITH@sakilacustomer.org';

CREATE INDEX idx_customer_email ON customer (email);

-- Same query, now with an index available.
EXPLAIN ANALYZE SELECT * FROM customer WHERE email = 'MARY.SMITH@sakilacustomer.org';

The second plan should show Index Scan using idx_customer_email instead of Seq Scan on customer — and, on a table this small (599 rows), the actual time difference may be tiny (sequential scans on small tables are already fast); the benefit compounds dramatically as table size grows, which is exactly why this module keeps returning to EXPLAIN ANALYZE — "does this index actually get used, and does it actually help" is an empirical question, not something to assume from syntax alone.

What operations a B-tree index actually accelerates

=, <, <=, >, >=, BETWEEN, and sorting (ORDER BY) on the indexed column. Not LIKE '%pattern%' with a leading wildcard — here's precisely why: a B-tree is sorted by the whole value, so it can — in principle — jump straight to values starting with 'ACE' (LIKE 'ACE%', a prefix match), but it has no way to jump to "contains ACE anywhere," since that's not a property the sort order exposes:

-- B-tree CANNOT help, no matter what: no leading anchor, sort order is
-- useless here — true regardless of index type or collation.
EXPLAIN SELECT * FROM film WHERE title LIKE '%GOLDFINGER%';

A real, non-obvious catch on the prefix case: a plain B-tree index on a text column, under any locale-aware collation (Postgres's default — check yours with SHOW lc_collate), does not actually accelerate LIKE 'ACE%', even though the reasoning above says it should be able to. This is because locale-aware string sorting doesn't always agree with simple byte-order prefix matching (accents, case rules, and locale-specific collation rules can reorder strings in ways that break the "jump to the prefix" shortcut). Proof, on pagila's default locale:

CREATE INDEX idx_film_title ON film (title);
EXPLAIN SELECT * FROM film WHERE title LIKE 'ACE%';
-- Still a Seq Scan — the plain index doesn't help this query at all.

The fix: index the column with the text_pattern_ops operator class specifically, which sorts by raw byte value instead of locale rules — exactly what prefix matching needs:

DROP INDEX idx_film_title;
CREATE INDEX idx_film_title_pattern ON film (title text_pattern_ops);
EXPLAIN SELECT * FROM film WHERE title LIKE 'ACE%';
-- Now: Index Scan, condition rewritten internally as a range
-- (title >= 'ACE' AND title < 'ACF').

The general lesson under the specific fix: "a B-tree index exists on this column" is not the same question as "this specific query can actually use it" — the operator class, the collation, and the exact predicate shape all matter, and EXPLAIN is the only reliable way to confirm an index is actually helping a given query rather than assuming it from the CREATE INDEX statement alone.

Index-only scans: when the index alone is enough

If every column a query needs is present in the index itself, the engine never needs to touch the underlying table (the "heap") at all — this is an Index Only Scan, visibly faster than an ordinary Index Scan because it skips a whole extra round of row lookups. This needs a column selective enough that the planner actually prefers the index over a sequential scan — rental.rental_date on the 16,044-row rental table is a good candidate (pagila's film.rental_rate only has 3 distinct values, too low-cardinality for the planner to ever prefer an index over a seq scan on a 1000-row table — worth knowing that "add an index" doesn't automatically mean "the planner will use it," exactly the point the previous section just made):

CREATE INDEX idx_rental_date ON rental (rental_date);

-- Needs ONLY rental_date -- the index alone can answer this fully.
EXPLAIN ANALYZE SELECT rental_date FROM rental WHERE rental_date > '2022-08-20';
-- Plan shows "Index Only Scan" and "Heap Fetches: 0" -- proof the heap
-- was never touched.

-- Needs rental_id too, which ISN'T in this index -- forces a heap lookup
-- per matching row (a regular Index Scan, not Index Only).
EXPLAIN ANALYZE SELECT rental_id, rental_date FROM rental WHERE rental_date > '2022-08-20';

(An Index Only Scan also depends on Postgres's visibility map being up to date — a detail tied to MVCC and VACUUM, Postgres internals beyond this course's scope — mentioned here so the term doesn't surprise you later; it doesn't change anything about how you'd write the query.)

Covering indexes: deliberately widening an index to enable Index Only Scan

A covering index deliberately includes extra columns specifically so more queries can become index-only scans — via the INCLUDE clause, which adds columns to the index without making them part of the sort key (so they don't help with filtering/sorting on those columns, only with avoiding the heap lookup):

DROP INDEX idx_rental_date;
CREATE INDEX idx_rental_date_covering ON rental (rental_date) INCLUDE (rental_id);

-- Now this CAN be an Index Only Scan -- both rental_date (the search
-- key) and rental_id (an INCLUDEd column) live in the index itself.
EXPLAIN ANALYZE SELECT rental_id, rental_date FROM rental WHERE rental_date > '2022-08-20';

This is a deliberate space-for-speed tradeoff — the index is now larger (every row's title is duplicated into it) in exchange for more queries avoiding the heap entirely. Not a default to reach for on every index; appropriate specifically when a query pattern is frequent and performance-critical enough to justify the extra storage and slightly slower writes (every index makes INSERT/UPDATE marginally more expensive, since the index has to be maintained too — covered fully in the performance-killers lesson later in this module).

Check yourself

  1. Why can a B-tree index accelerate LIKE 'ACE%' but not LIKE '%GOLDFINGER%'?
  2. What makes an Index Only Scan faster than an ordinary Index Scan?
  3. What does the INCLUDE clause on CREATE INDEX actually add to an index, and why doesn't it help with filtering on those included columns?
← Previous Next →