Chapter 6: Indexing Strategies: B-Tree, Hash, Composite, Covering

Why this matters

Chapter 5 showed an index turning a 121ms query into a 0.08ms one — but indexes aren't free, and "just add an index" without understanding what kind and why is a common source of both under-indexed slow queries and over-indexed slow writes. This chapter covers the actual mechanics well enough to make that trade-off deliberately.

Why an index works: the B-Tree, conceptually

[BEGINNER] A database index is a separate, ordered data structure that lets the database find rows matching a condition without scanning the entire table — directly analogous to a book's index letting you find a topic without reading every page. PostgreSQL's default index type, the B-Tree, keeps indexed values in a sorted, balanced tree structure, giving O(log n) lookup time instead of a full table scan's O(n).

Without an index: find customer_id = 42 by checking EVERY row -> O(n)

With a B-Tree index on customer_id:
                    [50]
                  /      \
              [25]        [75]
             /    \       /    \
          [10]   [40]  [60]   [90]
                   |
                (contains 42, found in a few comparisons, not a full scan)

Finding ANY value takes roughly log(n) comparisons -- for a million rows,
that's about 20 comparisons instead of up to a million.

CREATE INDEX idx_orders_customer_id ON orders(customer_id);

Hash indexes: faster for exact-match, useless for ranges

[BEGINNER] A hash index maps each value to a bucket via a hash function, giving very fast O(1) exact-match lookups — but a hash function deliberately scatters similar values unpredictably, so a hash index cannot support range queries (WHERE price_cents > 1000), ordering (ORDER BY), or partial matches (LIKE 'abc%') at all — only exact equality.

CREATE INDEX idx_sessions_token_hash ON sessions USING HASH (token);
-- Great for: WHERE token = 'abc123...' (exact match lookup, e.g., session token validation)
-- USELESS for: WHERE token > 'abc' or ORDER BY token

[IN PRACTICE] In practice, PostgreSQL's B-Tree is fast enough for most exact-match cases too, and supports ranges/ordering as a bonus — which is exactly why B-Tree is the default and hash indexes see comparatively narrow, deliberate use (specific high-volume exact-match-only lookup patterns, like session token validation, where the marginal difference matters).

Composite indexes: order matters

[SENIOR INSIGHT] A composite index spans multiple columns — and the order of columns in the index matters enormously, in a way that trips up even experienced engineers: a composite index on (customer_id, created_at) can efficiently serve a query filtering on customer_id alone, or on customer_id AND created_at together, but cannot efficiently serve a query filtering on created_at alone — because the index is physically sorted by customer_id first, then created_at within each customer_id group, exactly like a phone book sorted by last name then first name: you can efficiently find "Smith" or "Smith, John," but you can't efficiently find everyone named "John" across all last names without scanning the whole structure.

CREATE INDEX idx_orders_customer_created ON orders(customer_id, created_at);

-- FAST: uses the index fully (filters on the leading column)
SELECT * FROM orders WHERE customer_id = 42;

-- FAST: uses the index fully (filters on both columns, in index order)
SELECT * FROM orders WHERE customer_id = 42 AND created_at > '2026-01-01';

-- SLOW: cannot use this index effectively at all (skips the leading column)
SELECT * FROM orders WHERE created_at > '2026-01-01';

The rule of thumb: order composite index columns by putting the column(s) most commonly used for exact-match equality filtering first, and range/sort columns last — matching the most common query patterns against the table, not an arbitrary or alphabetical ordering.

Covering indexes: avoiding a second lookup entirely

[BEGINNER] Normally, once an index locates a matching row's location, the database still performs a second step — a heap fetch — to retrieve the row's actual full data from the table itself, since the index typically only stores the indexed column(s) plus a pointer to the row. A covering index includes every column a specific query needs directly in the index itself, letting PostgreSQL answer the query entirely from the index, skipping the heap fetch step completely (visible in an EXPLAIN plan as an "Index Only Scan" instead of a plain "Index Scan").

CREATE INDEX idx_orders_covering ON orders(customer_id) INCLUDE (total_cents, created_at);

-- This query can be answered ENTIRELY from the index — no heap fetch needed at all:
SELECT total_cents, created_at FROM orders WHERE customer_id = 42;

The real cost of an index: writes get slower

[SENIOR INSIGHT] Every index must be updated on every INSERT, UPDATE, or DELETE affecting its indexed column(s) — this is a genuine, often under-appreciated cost. A table with ten indexes pays the write-cost of maintaining all ten on every single insert, even though a given query only ever benefits from one of them. This is the real trade-off indexing represents: faster reads, slower writes, and additional storage — which is exactly why indexing shouldn't be applied reflexively to every column "just in case," but deliberately, informed by actual, observed query patterns (via EXPLAIN ANALYZE, Chapter 5) rather than speculation.

Common mistakes

1. Adding an index to every column "just in case it helps a future query" without evidence from actual query patterns — this pays a real, ongoing write-performance and storage cost for a benefit that may never materialize (the same premature-optimization theme running through this entire book series, applied to schema design specifically).
2. Choosing the wrong column order in a composite index, not realizing a query filtering only on the trailing column gets no benefit from the index at all.
3. Reaching for a hash index by default, not realizing it can't support range queries or ordering — a common, easy-to-avoid mistake once the B-Tree-vs-hash distinction is understood clearly.
4. Not periodically reviewing and removing unused indexes — an index that no query actually benefits from is pure write-performance and storage cost with zero read-performance payoff, and this tends to accumulate silently as a schema evolves and query patterns change over time.

Checklist: indexing deliberately

1. Add an index based on observed slow-query patterns (via EXPLAIN ANALYZE), not speculation about what might someday be queried.
2. For composite indexes, order columns by exact-match-equality-first, range/sort-columns-last, matching actual query filter patterns against the table.
3. Consider a covering index (INCLUDE) for a frequently-run, performance-critical query where an "Index Only Scan" (avoiding the heap fetch) would provide a meaningful additional speedup.
4. Periodically audit indexes for actual usage (PostgreSQL's pg_stat_user_indexes shows index usage statistics) and remove ones that aren't providing real read-performance benefit relative to their write-cost.

Discussion / interview questions

1. "How does a B-Tree index make a lookup faster than a full table scan?" Strong answer: Keeps indexed values in a sorted, balanced tree structure, enabling roughly logarithmic-time lookups (a handful of comparisons even for millions of rows) instead of linear-time scanning of every row.

2. "Why can't a hash index support a range query like WHERE price > 1000?" Strong answer: A hash function deliberately scatters similar values into unpredictable, unordered buckets to achieve fast exact-match lookups — there's no way to efficiently find "all values greater than X" in a structure with no inherent ordering, unlike a B-Tree.

3. "You have a composite index on (customer_id, created_at). Will a query filtering only on created_at use this index efficiently?" Strong answer: No — a composite index is physically ordered by its leading column first; skipping the leading column in the filter means the index can't be used efficiently for that query, the same way a phone book sorted by last-then-first name can't efficiently answer "find everyone named John."

4. "What's the trade-off of adding more indexes to a table?" Strong answer: Faster reads for queries the index actually serves, at the cost of slower writes (every index must be updated on every insert/update/delete affecting its columns) and additional storage — indexes should be added based on real query patterns, not speculatively.

Chapter summary / cheat sheet

• B-Tree (PostgreSQL's default): sorted structure, O(log n) lookups, supports range queries and ordering — the right default for most cases.
• Hash index: O(1) exact-match only, no range/ordering support — narrow, deliberate use cases (like session token lookups).
• Composite index: column order matters — leading column(s) should match the most common exact-match filter patterns; a query skipping the leading column gets little to no benefit.
• Covering index (INCLUDE): lets a query be answered entirely from the index (an "Index Only Scan"), skipping the extra heap-fetch step.
• Every index speeds up reads but slows down writes and adds storage — index deliberately, based on observed query patterns (EXPLAIN ANALYZE), not speculatively, and periodically audit for unused indexes.

---