How Things Work

Database Indexing Deep Dive

Why a query goes from seconds to sub-millisecond — sequential scans vs B-tree seeks, composite and covering indexes, selectivity, and reading the query plan.

How It Works

An index is a sorted side structure that lets a database find rows without reading the whole table — turning an O(n) scan into an O(log n) seek. Indexes are the single biggest lever on query performance, but they cost write throughput and storage, so they must be chosen for your actual query patterns and verified with the query planner.

The Problem: Sequential Scan

Table rows are stored roughly in insertion order, not sorted by any column. To find rows matching a WHERE clause, the database must read every row and check it — a sequential scan, O(n). At a few rows it's instant; at millions it's a full-table read on every query.

The Fix: A B-Tree Index

An index is a separate, sorted data structure (usually a B-tree) mapping column values to row locations. Because it's sorted and balanced, the engine narrows the search by half at each level — O(log n). Finding one row among a billion takes ~30 steps instead of a billion.

Composite & Covering Indexes

A composite index on (a, b) sorts by a then b, and follows the leftmost-prefix rule — it helps queries filtering on a, or a+b, but not b alone. A covering index includes all the columns a query needs, so the engine answers from the index alone without touching the table ('index-only scan').

The Cost & the Planner

Indexes aren't free: every INSERT/UPDATE/DELETE must also update each index, and indexes consume storage. The query planner uses statistics to decide whether an index actually helps — for low-selectivity predicates (matching most rows) a scan can be cheaper. Always verify with EXPLAIN.

Key Concepts

🌳B-Tree Index

A balanced, sorted tree mapping values to row locations. Gives O(log n) lookups, range scans, and ordering. The default index type.

📜Sequential Scan

Reading every row to find matches — O(n). What happens with no usable index.

🧩Composite Index

An index on multiple columns (a, b). Useful left-to-right (leftmost-prefix rule); column order is a design choice.

🛡️Covering Index

An index that includes every column a query needs, so it's answered from the index alone (index-only scan).

🎯Selectivity

How many rows a predicate matches. High selectivity (few matches) makes an index worthwhile; low selectivity favors a scan.

🔍EXPLAIN / Query Plan

The optimizer's chosen execution strategy (scan vs index, joins). The tool for diagnosing slow queries.

Creating & reasoning about indexes

tsx

1-- A query that scans the whole table:
2SELECT * FROM users WHERE email = 'a@b.com';   -- Seq Scan, O(n)
3
4-- Add a B-tree index → the planner can seek directly:
5CREATE INDEX idx_users_email ON users(email);  -- Index Scan, O(log n)
6
7-- Composite index: order matters! Follows the "leftmost prefix" rule.
8CREATE INDEX idx_orders_user_date ON orders(user_id, created_at);
9--  ✅ uses index:  WHERE user_id = 7 AND created_at > '2024-01-01'
10--  ✅ uses index:  WHERE user_id = 7
11--  ❌ can't use it: WHERE created_at > '2024-01-01'   (skips user_id)
12
13-- Covering index: include columns so the row isn't even read
14CREATE INDEX idx_cover ON orders(user_id) INCLUDE (status, total);
15
16-- Always inspect the plan before trusting it:
17EXPLAIN ANALYZE SELECT * FROM users WHERE email = 'a@b.com';

💡

Why This Matters

Indexing is the most common real-world database performance fix and a frequent interview topic. Understanding B-trees, the leftmost-prefix rule, covering indexes, selectivity, and EXPLAIN output is what lets you turn a multi-second query into a fast one — and avoid the over-indexing that cripples writes.

Common Pitfalls

⚠No index on filtered/joined columns — silent O(n) scans that only hurt once the table grows.

⚠Wrong column order in a composite index — the leftmost-prefix rule means (a,b) won't help a query on b alone.

⚠Over-indexing — every index slows writes and adds storage; unused indexes are pure cost.

⚠Functions/implicit casts on indexed columns (WHERE LOWER(email)=…) prevent the index from being used.

⚠Trusting intuition over EXPLAIN — the planner may pick a scan for low-selectivity predicates.

Real-World Use Cases

1The Query That Got Slow Overnight

Scenario

A login lookup `WHERE email = ?` was instant in development but takes 4 seconds in production after the users table grew to 5 million rows.

Problem

There was no index on email, so every login triggered a sequential scan of all 5M rows. It was invisible at small scale and became a production-wide bottleneck as data grew — the classic O(n) trap.

Solution

Add a B-tree index on email. The lookup drops from a 5M-row scan to a ~23-step index seek (log₂ 5M), returning in under a millisecond. Confirm with EXPLAIN ANALYZE that the plan switched from Seq Scan to Index Scan.

💡

Takeaway: Index the columns you filter and join on. Performance problems that 'appear' over time are usually missing indexes whose O(n) cost only hurts once the table is big.

2Too Many Indexes Killed Writes

Scenario

A team added an index for every reporting query. Reads got fast, but bulk imports and high-volume writes slowed to a crawl.

Problem

Each of the 12 indexes on the orders table had to be updated on every INSERT and UPDATE. Write amplification turned a single row write into 13 structure updates, and the indexes bloated storage.

Solution

Audit index usage (drop unused ones), replace several single-column indexes with a few well-ordered composite/covering indexes that serve multiple queries, and avoid indexing low-selectivity columns. Writes recovered while keeping the important reads fast.

💡

Takeaway: Indexes trade write speed and storage for read speed. Add them deliberately for real query patterns — every extra index taxes every write, so more is not better.

Join the discussion

Comments

Loading comments...

Cookie preferences

We use essential cookies for sign-in and preferences. With your permission, we also use basic analytics to improve lessons.