How database indexes work: from full table scan to B-Tree

You're searching for a single email in a table with a million rows. The query takes four seconds. The database isn't slow; you just didn't give it directions.

Full table scan

Without an index, the database has no choice: it reads rows one by one from start to finish. The record you're looking for might be in the very last row, so it has to look at all of them. This is called a full table scan—a million rows, a million comparisons.

The phone book analogy

When looking for someone in a phone book, do you flip through page by page? No, you go alphabetically and jump straight to the letter. An index is exactly that: a pre-sorted copy of the data. This copy lives in a tree structure called a B-Tree and cuts the search space in half at each step. Instead of a million comparisons, about twenty are enough.

The one-line fix

CREATE INDEX idx_users_email ON users (email);

The exact same query drops from four seconds down to two milliseconds—roughly two thousand times faster. Not a bad gain for a single-line migration.

Indexes aren't a silver bullet

But slapping an index on every column isn't the solution: every write operation has to update this index too, meaning INSERT/UPDATE queries get slower. On top of that, certain query patterns won't use the index at all—the two most classic ones:

• A LIKE '%istanbul' pattern starting with a percentage sign (matching from the end disables the index; LIKE 'istanbul%' is fine)
• Wrapping a column in a function: WHERE LOWER(email) = ...—the index is on email, not LOWER(email)

Wrapping up

When you see a slow query, run EXPLAIN ANALYZE first. Most of the time, the problem isn't your code—it's a missing or misconfigured index.