Why does an index speed up a query?

This is the first database lesson. The goal: get to the point where you can explain this out loud, with a diagram, under pressure — because that is what an interview tests. By the end you should hold one idea firmly: an index trades write speed and storage for read speed, and it only helps when the column is selective.

The problem an index solves

Imagine a phone book with 10,000 names — in random order. To find “Smith”, you flip through every page. That is a sequential scan (full table scan): the database reads every row and checks whether it matches. The cost grows with the table: O(n).

Now imagine the phone book is sorted alphabetically. You jump straight to the S section. That is what an index does: it keeps a sorted copy of a column, with pointers back to the full rows.

The structure usually used is a B-tree — a balanced tree. It stays balanced, so the height grows logarithmically. For a million rows the tree is only about 20 levels deep, so a lookup is ~20 comparisons instead of a million. That is O(log n).

The tradeoff nobody mentions in interviews

Indexes are not free. The candidate who says “just add an index” and stops — fails. A strong answer names the costs:

• Slower writes. Every INSERT, UPDATE, DELETE must also update every index on the table.
• More storage. Each index is a separate sorted copy of data.
• Useless or worse on low-selectivity columns. An index on a boolean active column barely narrows the search, so the planner often ignores it and does a sequential scan anyway.

Index the columns you query. Don’t index everything. Indexes cost writes.

When the index is silently ignored

These are the traps that make “I added an index but it didn’t help” a real-world bug:

• WHERE email LIKE '%son' — a leading wildcard. The B-tree is sorted by prefix; without a known prefix it cannot seek, so it falls back to a scan.
• WHERE LOWER(email) = 'x' — a function on the column. The index is on email, not on LOWER(email). You’d need an expression index: CREATE INDEX ON users(LOWER(email)).
• Low selectivity — a column with two distinct values across a million rows.

Check your understanding

Three quick retrieval checks. Don’t look back up the page — answer from memory. That effort is what makes it stick.