Database Indexes

Trading write speed for read speed

Without an index, the only way to find rows matching a condition is a full table scan — read every row, check each one. On a million-row table that is a million disk reads. An index is a separate sorted structure that lets the database find matching rows in O(log n) instead of O(n), the same way a book's index lets you find a topic without reading every page.

How a B-tree index works

The default index type is a B-tree (balanced tree). It keeps the indexed column's values sorted in a tree structure:

                [ M ]
              /   |   \
         [F]    [T]    [Z]
        / \     / \     / \
      ...  ... ... ... ...  ...
      -- leaf nodes point to the actual table rows

Each lookup descends the tree in O(log n) comparisons, then follows a pointer to the matching table row. Range queries (WHERE age BETWEEN 20 AND 30) also benefit, because the leaves are linked in sorted order.

When to index

• Columns used in WHERE clauses, JOIN conditions, or ORDER BY.
• Foreign keys (speeds up joins and cascade operations).
• Columns with high selectivity — many distinct values, so the index narrows the search sharply. A boolean is_active column rarely benefits; an email column does.

Composite indexes and column order

A composite index covers multiple columns. Order matters enormously: the index is sorted by the first column, then the second, and so on — exactly like a phone book sorted by last name, then first name.

CREATE INDEX idx ON orders(customer_id, created_at);

-- Uses the index:
WHERE customer_id = 42                       -- leftmost column
WHERE customer_id = 42 AND created_at > ...  -- leftmost + next

-- CANNOT use the index efficiently:
WHERE created_at > '2025-01-01'             -- skips the leftmost column
                                              -- (like searching a phone book
                                              --  by first name only)

This is the leftmost prefix rule: an index is usable only for queries that filter on a leading prefix of its columns.

The cost of indexes

Indexes are not free. Every INSERT, UPDATE, or DELETE must update every affected index — this is write amplification. Indexes also consume disk and memory (the index must fit in the buffer pool to help).

-- Each of these slows down writes and uses storage:
CREATE INDEX ON orders(customer_id);
CREATE INDEX ON orders(status);
CREATE INDEX ON orders(created_at);
CREATE INDEX ON orders(customer_id, created_at);

Index for your queries, not by reflex. Every index accelerates some reads but taxes every write. Profile slow queries, add the minimal set of indexes that resolves them, and drop indexes that no query uses — they are dead weight on every insert.

When NOT to index

• Small tables — a sequential scan is faster than index lookup overhead.
• Low-selectivity columns (a flag that is 99% true).
• Frequently updated columns where write cost dominates.
• Tables that are write-heavy and read-light.