DEV Community

The Byte Mechanics
The Byte Mechanics

Posted on

From 9 Seconds to 2 Milliseconds: Database Indexes Explained

#backend #database #performance #sql

How an index works, why it's a B-tree, and the one mistake that makes the database ignore it

This query took nine seconds:

SELECT * FROM users WHERE email = 'priya@example.com';
Enter fullscreen mode Exit fullscreen mode

One line of SQL made it two milliseconds. That's four thousand times faster, with no new hardware and no code changes. That line creates a database index.

But here's the twist: you can have exactly the right index, and the database will still ignore it, because of one tiny thing in your query. By the end of this article you'll know how indexes work, and you'll spot that mistake in your own code. If you'd rather watch, here's the 7-minute animated version:

1. Why it took nine seconds

The users table has ten million rows. You asked for one email. With no index, the database has no idea where that row is, so it does the only thing it can: it reads every row and checks each one. That's called a full table scan.

And the data isn't read row by row from memory. It's read in pages from disk, thousands of them. Ten million checks to find one person.

You'd never search a phone book like that. So why does your database?

2. The phone book trick

Imagine finding "Priya" in a phone book by reading every name from page one. Nobody does that. You open near the middle. "M"? Priya comes after M, so you jump right. "R"? Too far, jump back. Within a few jumps, you're on the right page.

That only works because the names are sorted. Sorting is what lets you skip almost everything.

An index is exactly that: a sorted copy of one column, kept separately, that points back to the full rows.

CREATE INDEX idx_email ON users(email);
Enter fullscreen mode Exit fullscreen mode

But a database doesn't store it as a list. It uses a tree.

3. The B-tree

Most databases store indexes as a B-tree. At the top is a root page holding a few hundred keys that split the range: everything before "F" is down this branch, everything from "F" to "M" down that one. At the bottom, the leaf pages hold the actual emails, in order, each with a pointer to its row.

Because every page holds hundreds of keys, the tree stays incredibly short. Ten million rows fit in about three or four levels. So instead of ten million checks, the database reads three or four pages. That's the jump from nine seconds to two milliseconds.

4. Prove it with EXPLAIN

You don't have to guess. Put the word EXPLAIN in front of your query, and the database shows you its plan.

EXPLAIN SELECT * FROM users WHERE email = 'priya@example.com';
Enter fullscreen mode Exit fullscreen mode

Before the index, it says Seq Scan: read everything. After the index, it says Index Scan using idx_email. Same query, completely different plan.

Make this a habit: any query that feels slow, run EXPLAIN first. Because sometimes you'll add an index, run EXPLAIN, and still see "Seq Scan". And you'll wonder why.

5. Column order matters

Indexes can cover more than one column. An index on (last_name, first_name) is like a phone book sorted by surname, and then by first name within each surname. That's perfect for finding "Smith, Priya". It also works for every "Smith".

But try to find everyone named "Priya" with any surname, and the sort order is useless. They're scattered through the whole book.

This is the leftmost-prefix rule: a multi-column index helps only when your query uses the columns from the left. And that's just one of the ways an index gets skipped. The most common one is far sneakier.

6. Where indexes quietly stop working

Remember, the index is a sorted list of the exact values in that column. The database can only jump through it if your query asks about those exact values.

The moment your query transforms the column first, the sorted order no longer helps. The database can't jump anymore. It goes back to reading every row, and it doesn't warn you.

7. Test yourself

You have an index on the email column. Users sometimes type their email with capital letters, so the code does this:

SELECT * FROM users WHERE LOWER(email) = 'priya@example.com';
Enter fullscreen mode Exit fullscreen mode

Does the database use the email index for this query? Decide before you read on.

8. The answer is no

The index stores emails exactly as written: some with capitals, some without. LOWER(email) is a different value that isn't in the index at all, so the database has to compute it for every row. Full scan, nine seconds again.

The same thing happens with a leading wildcard, like LIKE '%@gmail.com', because the start of the value is unknown. And it happens when you compare a text column to a number and the database has to convert types.

The fix has two options. Store the value already normalised, lowercase on the way in. Or create an index on the expression itself:

CREATE INDEX idx_email_lower ON users (LOWER(email));
Enter fullscreen mode Exit fullscreen mode

Then run EXPLAIN again and confirm.

9. Indexes aren't free

So, if indexes are this powerful, why not index every column? Because every index is another sorted structure the database must keep up to date. Insert a row, and every index on that table gets updated too. Ten indexes means eleven writes for every insert. They also take disk space and memory.

And some indexes barely help. Index a column with only two values, like true or false, and the database often decides scanning is cheaper anyway. So index the columns you actually filter by, join on and sort by. Check with EXPLAIN. And remove indexes nobody uses.

10. How real databases build on this

In PostgreSQL and MySQL, the default index is a B-tree, exactly what we drew. In MySQL's InnoDB, the table itself is stored in primary key order, so looking up by primary key goes straight to the row.

If an index contains every column a query needs, the database can answer from the index alone, without touching the table. That's a covering index.

And for special data there are special indexes: hash indexes for exact matches, and in PostgreSQL, GIN indexes for things like full-text search and JSON.

11. Database indexes in one screen

  • Without an index, the database scans every row.

  • An index is a sorted B-tree that finds a row in a few page reads.

  • Use EXPLAIN to check the plan.

  • Multi-column indexes work from the left.

  • Don't wrap the indexed column in a function, a leading wildcard or a type conversion.

  • Every index costs you on writes, so add the ones you need.

Now the query is fast. But between your user and your database is a network, and every request crosses it.

▶️ Watch the animated version: Database Indexes Explained (YouTube)

Previous: From 3 Seconds to 3 Milliseconds: Caching Explained

*If this helped, leave a comment and follow The Byte Mechanics for more visual explainers.

About: The Byte Mechanics turns how software really works into short animated explainers: system design, backend and operating systems, one diagram at a time.

Top comments (0)