Indexes: The Database’s Table of Contents

An index is a data structure that lets the database find rows without scanning the whole table. The classic structure is a B-tree: a balanced, multi-way tree with thousands of keys per node, kept in sorted order so range queries (BETWEEN, >, <) are cheap. A full table is millions of rows; a B-tree of the same data is a few levels deep — the difference between reading megabytes and reading a handful of pages.

Indexes Don’t Store Answers, They Store Pointers

A secondary index holds key → row location pairs. The index lets you find the location of the matching rows quickly, but retrieving the actual row data usually means a follow-up read of the table (a lookup). This is why an index speeds up WHERE id = 7 but a query that asks for columns not in the index pays a second read per row — sometimes a plain table scan is cheaper.

B-Tree Fanout: Why Height Stays Tiny

The reason a B-tree on millions of rows is only 3–4 levels deep is fanout — how many children each node points to. A node holds thousands of keys because disk reads are page-sized (typically 8–16 KB), and each node is one page. The tree’s height is:

height ≈ log_fanout(rows)

Concretely, with 8 KB pages and keys that pack ~100 entries per node, a fanout of ~100 means:

• Level 0 (root): 100 keys.
• Level 1: 100 × 100 = 10,000 keys.
• Level 2: 100³ = 1,000,000 keys.
• Level 3: 100⁴ = 100,000,000 keys.

So a table with 100 million rows is only 4 levels deep — a lookup touches 4 pages (one per level), and the top levels stay hot in memory. Compare a binary tree: log2(100M) ≈ 27 — 27 random disk reads per lookup. The multi-way node is precisely why B-trees (not binary trees) dominate on disk: each level costs one page read, and fanout buys depth.

Hash Indexes: Exact Matches Only

A hash index applies a hash function to the key and stores entries in hash buckets. It answers equality lookups (WHERE key = x) in expected O(1) — one hash, one bucket probe, usually one page. What it cannot do:

• Range queries — >/</BETWEEN/ORDER BY need sorted order, which a hash has none of. (The B-tree is the range-workhorse.)
• Prefix / LIKE scans — LIKE 'abc%' walks sorted order; a hash has no order to walk.
• Leftmost-prefix matching on composites — hashing the whole key pair means WHERE (a) alone doesn’t match hash(a,b).

Databases that expose explicit hash indexes (PostgreSQL USING hash, MySQL MEMORY tables) use them for high-cardinality equality lookups — e.g. an id = ? hot path where you never range-scan. In practice most engines default to B-trees because they handle equality and range; the hash wins only when you need absolute maximum equality throughput and can give up ordering.

Clustered vs Non-Clustered

• Clustered index — the table’s data is physically ordered by the key; there is at most one per table (usually the primary key). Lookups by key are the fastest possible — the row is right there.
• Non-clustered index — a separate structure holding key + pointer to the row. Many per table. Each lookup costs an extra page read (or a scan of the index itself if it’s covering, below).

Composite Indexes: Column Order Is Everything

An index on (country, city, street) can serve lookups by (country), (country, city), and (country, city, street) — but not by (city) alone or (street, city). The leftmost-prefix rule is the single most consequential indexing fact to internalize:

• WHERE country = 'US' AND city = 'NY' — uses the index.
• WHERE city = 'NY' — cannot use it (skips the leading column).

Choose the leading column for the column with the most selective/equality filters; equality filters before range filters. An index that covers every column a query needs is a covering index — the database never touches the table at all.

EXPLAIN: Reading the Query Plan

The planner chooses how to execute a query — and it may not pick the index you expect. EXPLAIN ANALYZE shows the plan with actual timings:

EXPLAIN ANALYZE SELECT * FROM orders WHERE user_id = 42;

• Seq Scan — reads every row. Fine for small tables, catastrophic for big ones (or when your WHERE column has no index).
• Index Scan — finds row locations in the index, then reads each row.
• Index Only Scan — the covering case: the index alone answers the query.
• Bitmap Heap Scan — index first, then batched table reads; the planner’s way of handling many matches without per-row random I/O.

Never optimize blind — EXPLAIN ANALYZE before and after an index tells you the truth. The most common “why is it slow” answers: missing index on the WHERE/JOIN column, a function wrapping the indexed column (WHERE lower(email) = ... disables the index unless it’s a functional index), or a %...% LIKE that defeats the B-tree.

Indexing Strategies

• Index columns used in WHERE equality, JOIN keys, and ORDER BY/GROUP BY.
• Prefer selective indexes: an index on a column where most rows share one value (status = 'active' for 99% of rows) rarely helps.
• Watch for write amplification: every INSERT/UPDATE must maintain every index on the table. A table with 6 indexes pays 6 maintenance costs per write.
• Over-indexing is a real failure mode — the query cache, the planner, and the storage all get slower. Drop indexes the plans show you’re not using.
• Rare-value tricks like partial indexes (WHERE deleted_at IS NULL) keep index size proportional to what you actually query.

Worked Example

A table with 5M orders. SELECT * FROM orders WHERE user_id = 42 AND created_at > now() - interval '7 days' is slow. Add:

CREATE INDEX idx_orders_user_created
  ON orders (user_id, created_at);

The composite index serves the equality user_id first, then the range created_at — two index seeks, no table scan. EXPLAIN ANALYZE should flip from Seq Scan (5M rows) to Index Scan (a few dozen rows), and latency drops from hundreds of milliseconds to microseconds.

Practice Trajectory

1. Run EXPLAIN ANALYZE on a slow query in a test database and read the actual vs estimated row counts.
2. Add the obviously-missing index; re-run the plan and record the improvement.
3. Take a composite-indexed query and reorder the columns — watch the plan fall back to a scan.
4. Introduce a function-wrapped column (WHERE lower(name) = ...) and observe the index being ignored.
5. Drop an unused index and measure the write-path improvement on a bulk insert.

When It’s the Right Tool