Database indexing

An index is an extra data structure that lets the database find rows without scanning the whole table.

Why it matters

Finding one row among 100 million by checking every row takes seconds. Users and other services can't wait that long, and the database burns CPU doing it.

The idea

Most databases use B-tree indexes: sorted, balanced trees that find a value in a few steps and also support ranges and sorting. Indexes make reads fast but writes slower, because every index must be updated, and they use extra storage. Composite indexes cover several columns, and the column order matters.

The index at the back of a textbook: you look up 'eigenvalue — page 212' instead of reading every page.

A book's index is written once. A database index is updated on every insert and update, which is why adding indexes to a write-heavy table has a real cost.

How it works

  1. Without an index, WHERE email = 'a@b.com' reads every row: a full table scan.
  2. CREATE INDEX on email builds a B-tree: a sorted tree where each step down cuts the search space enormously.
  3. With 100 million rows the tree is only about 3–4 levels deep, so finding the row takes a handful of reads instead of millions.
  4. The index stores the email plus a pointer to the row, and the database follows that pointer.
  5. Every INSERT, or UPDATE of the email, must also update the tree, which costs time.
  6. EXPLAIN shows the plan: 'Index Scan' is good; 'Seq Scan' on a big table means no useful index was found.

Example

SELECT * FROM orders WHERE user_id = 42 ORDER BY created_at DESC LIMIT 20 is fast with an index on (user_id, created_at). Without it, the database scans millions of rows.

Key points

Common mistakes

Not true: The order of the columns in a composite index makes no difference.
In fact: An index on (a, b) is sorted by a first, so it helps queries on a, or on a and b, but not on b alone. Put first the column your queries always filter on.

Not true: WHERE LOWER(email) = … can use a normal index on email.
In fact: The function hides the column, so the index can't be used and every row is checked. Compare the bare column with a value instead, for example by storing emails in lower case.

In the interview

I'd add indexes that match the main queries: for 'latest orders for a user', a composite index on user_id and created_at. I'd check with EXPLAIN, and avoid indexing everything, since every index slows writes.

Part of Unit 3: Data: databases, storage and scaling data in the free System Design course.