Database Indexing: Making Queries Fast

📘 Chapter 4: Databases & Storage ⏱️ 10 min read 🏗️ Lesson 015

Your database has 50 million rows. Without an index, finding one row means scanning all 50 million. With the right index, it takes about 26 steps. That's the difference between 3 seconds and 5 milliseconds. Indexing is the single highest-leverage performance optimization in most systems.

What Is an Index?

An index is a separate data structure that maintains a sorted reference to your data. Think of it like the index at the back of a textbook — instead of reading every page to find "B-tree," you look up "B" in the alphabetical index, get page 142, and go directly there.

The Core Trade-off

Reads get faster — lookups go from O(n) to O(log n).

Writes get slower — every INSERT/UPDATE must also update the index.

Storage increases — the index itself takes disk space.

Without Index vs With Index

Finding "user_id = 42" in 1 Million Rows Without Index: Full Table Scan row 1: user_id=7, name="..." ✗ row 2: user_id=91, name="..." ✗ row 3: user_id=23, name="..." ✗ row 4: user_id=55, name="..." ✗ ⋮ scan 999,996 more rows ⋮ row 999999: user_id=42 ✓ FOUND! ~1,000,000 comparisons ⏱️ ~3 seconds With Index: B-tree Lookup [1-500K|500K-1M] ← step 1 [1-250K|250K-500K] ← step 2 [1-1K|1K-2K|...] ← step 3 ⋮ (steps 4-19) id=42 → row ptr ← step 20 ~20 comparisons (log₂ 1M) ⏱️ ~5 milliseconds Index makes this query 600x faster
Full table scan checks every row. B-tree index eliminates half the remaining candidates at each step.

B-Tree Structure

The most common index structure is the B-tree (balanced tree). Every database you'll use (PostgreSQL, MySQL, SQLite) defaults to B-tree indexes.

B-Tree Index Structure | 25 | 50 | 75 | Root | 5 | 10 | 18 | | 30 | 38 | 42 | | 55 | 62 | 70 | | 80 | 88 | 95 | 30→row | 38→row | 42→row leaf node (has row pointers) Search path for key=42: Root → Internal → Leaf (3 disk reads) B-trees stay balanced: all leaves are at the same depth. Lookup is always O(log n).
B-tree: sorted keys in nodes, with pointers to child nodes. Each level narrows the search space.

Types of Indexes

Index Type What It Does Example
Primary Key Unique identifier, auto-created. Clustered (data sorted by PK). id column
Secondary Index on a non-PK column for faster lookups. CREATE INDEX idx_email ON users(email)
Composite Index on multiple columns (order matters!). CREATE INDEX idx ON orders(user_id, created_at)
Covering Index contains all columns needed by a query — no table lookup needed. CREATE INDEX idx ON orders(user_id, status) INCLUDE (total)

Composite Index: Order Matters!

An index on (user_id, created_at) helps queries that filter by:

  • ✅ WHERE user_id = 5 (uses leftmost prefix)
  • ✅ WHERE user_id = 5 AND created_at > '2024-01-01' (uses both)
  • ❌ WHERE created_at > '2024-01-01' (can't skip the leftmost column)

Think of it like a phone book sorted by last name, then first name. You can find all "Smiths" easily, but finding all "Johns" across all last names still requires scanning.

The Write Penalty

Indexes aren't free. Every index adds cost to writes:

INSERT INTO orders (user_id, product_id, total, status, created_at)
VALUES (42, 7, 99.99, 'pending', NOW());

-- Behind the scenes, the database must also:
-- 1. Update the primary key index
-- 2. Update idx_user_id index
-- 3. Update idx_status index
-- 4. Update idx_created_at index
-- 5. Update idx_user_status composite index
-- That's 5 index updates per INSERT!

Rule of thumb: A table with 5+ indexes will have noticeably slower writes. Only index columns you actually query on.

What to Index

Look at Your Queries

  • WHERE clauses — WHERE status = 'active' → index status
  • JOIN conditions — JOIN orders ON users.id = orders.user_id → index orders.user_id
  • ORDER BY — ORDER BY created_at DESC → index created_at
  • High cardinality — Indexing a boolean (2 values) helps less than indexing email (millions of values)

E-Commerce Query: 3 Seconds → 5ms

An e-commerce app had this slow query on a 20M-row orders table:

SELECT * FROM orders
WHERE user_id = 12345
  AND status = 'completed'
ORDER BY created_at DESC
LIMIT 10;

Before: Full table scan, 3.2 seconds. The database checked all 20M rows.

Fix: CREATE INDEX idx_user_status_date ON orders(user_id, status, created_at DESC);

After: 4.7ms. The composite index lets the database jump directly to user 12345's completed orders, already sorted by date. It reads exactly 10 rows.

Reading EXPLAIN Plans

Use EXPLAIN to see how the database executes your query:

EXPLAIN SELECT * FROM orders WHERE user_id = 42;

-- Key things to look for:
-- ✅ "Index Scan" or "Index Only Scan" — using an index (good!)
-- ❌ "Seq Scan" — full table scan (bad on large tables)
-- ⚠️ "Bitmap Index Scan" — using index but reading many rows
-- 📊 "rows" estimate — how many rows the DB thinks it'll process

Interactive: B-Tree Insert Visualization

Insert values into the B-tree and watch it maintain balance. Each node holds at most 3 keys — when full, it splits.