Chapter 13: Indexes — What They Are and How They Work

Indexes are the single most important tool for database performance. They're the difference between a query taking 5 seconds and 5 milliseconds.

The Problem: Full Table Scan

Without an index, finding a row requires reading every page of the table:

SELECT * FROM users WHERE email = 'alice@example.com';

-- Without index: scan ALL pages (sequential scan)
-- 1 million rows, 100 rows/page = 10,000 pages to read
-- At 0.1ms per page (SSD) = 1 second

-- With index: look up directly
-- B-tree depth 3-4 = 3-4 page reads = 0.3-0.4ms

💡 Book Analogy

An index is like the index at the back of a textbook. Without it, finding "ACID" means reading every page. With it, you look up "ACID → page 247" and go directly there. A database index works the same way — it maps values to row locations.

What an Index Is (Physically)

An index is a separate data structure (stored in its own pages on disk) that maps column values to row locations (page number + offset).

Table "users" (heap — unordered): Page 0: [id=47,Alice] [id=12,Bob] [id=89,Charlie] Page 1: [id=3,Dave] [id=56,Eve] [id=23,Frank] Page 2: [id=91,Grace] [id=7,Heidi] [id=34,Ivan] Index on "id" (B-tree — sorted): ┌─────────────────────────────────────┐ │ [34, 56] │ ← root node │ / | \ │ │ [3,7,12] [23,34] [47,56,89,91] │ ← leaf nodes │ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ │ │ pointers to actual rows in heap │ └─────────────────────────────────────┘ Looking up id=23: Root: 23 < 34, go left... wait, 23 ≥ 23, go middle Leaf: found 23 → points to Page 1, offset 5 Read Page 1, get Frank. Done. (3 page reads total)

Creating Indexes

-- Basic index
CREATE INDEX idx_users_email ON users (email);

-- Unique index (also enforces uniqueness)
CREATE UNIQUE INDEX idx_users_email ON users (email);

-- Multi-column (composite) index
CREATE INDEX idx_orders_customer_date
    ON orders (customer_id, created_at DESC);

-- Partial index (only index active users)
CREATE INDEX idx_active_users ON users (email)
    WHERE active = true;

-- Index on expression
CREATE INDEX idx_users_lower_email ON users (LOWER(email));

When Indexes Help

WHERE column = value — exact lookup
WHERE column > value — range scan
WHERE column BETWEEN a AND b — range scan
ORDER BY column — already sorted in index
JOIN ... ON a.col = b.col — fast lookup of matching rows
WHERE column IN (a, b, c) — multiple lookups

When Indexes DON'T Help

WHERE column != value — must scan most of the index anyway
WHERE column LIKE '%suffix' — leading wildcard can't use index
WHERE function(column) = value — unless you have an expression index
Very small tables — sequential scan is faster than index overhead
Queries returning most of the table — sequential scan wins

The Cost of Indexes

⚠️ Indexes Aren't Free

Storage: each index takes disk space (often 10-30% of table size)
Write overhead: every INSERT/UPDATE/DELETE must also update all indexes
Maintenance: indexes can become bloated and need REINDEX

Rule of thumb: index columns you query on frequently. Don't index everything.

What to Index: The Rules

Primary keys — automatically indexed
Foreign keys — always index these (JOINs need them)
Columns in WHERE clauses — if queried frequently
Columns in ORDER BY — avoids sorting at query time
Columns in JOIN conditions — speeds up the join

Key Takeaways

Index = separate sorted data structure mapping values → row locations
Turns O(n) full scan into O(log n) lookup
Always index: primary keys (auto), foreign keys, frequent WHERE columns
Cost: extra storage + slower writes. Don't over-index.
Partial indexes and expression indexes for specialized queries
Composite indexes: column order matters (leftmost prefix rule)

← Previous: Design Patterns Next: B-Tree Internals →