Database Indexing: How One Line Makes Queries 1000x Faster

🔵 Fundamentals · Fresher-friendly → 🟠 senior nuance

Here's a magic trick that's not magic: a database query that takes 3 seconds can drop to 3 milliseconds by adding a single line — an index. Indexing is the highest-impact database skill you can learn, it comes up in nearly every interview, and it's genuinely simple once you see the picture. Let's build that picture from zero, then cover the trade-offs that separate juniors from seniors.

The problem: the full table scan

Imagine a users table with 10 million rows and you run SELECT * FROM users WHERE email = 'a@x.com'. Without an index, the database has no idea where that email is, so it does the only thing it can: reads every single row, top to bottom, checking each one. That's a full table scan — 10 million reads to find one row. Slow, and it gets slower as the table grows.

Analogy: finding a topic in a 1,000-page book by reading every page from page 1. Painful.

The fix: an index (the book's index)

Now add an index on email. The database builds a separate, sorted structure of every email pointing to where its row lives. To find a@x.com, it no longer scans — it does a fast lookup in the sorted structure (like flipping to "E" in a book's index) and jumps straight to the row.

The result: instead of scanning millions of rows, the database touches a handful. This is the difference between O(n) (grows with table size) and O(log n) (barely grows at all). On big tables, that's the 3-seconds-to-3-milliseconds jump.

How it works under the hood: the B-tree

🟠 Most database indexes are B-trees (balanced trees). You don't need the full theory, just the intuition: a B-tree keeps keys sorted and shallow, so any lookup takes only a few steps even over billions of rows — you start at the top and follow branches, halving the search space each step, exactly like looking up a word in a dictionary by opening near where it should be.

Because B-trees keep data sorted, an index doesn't just speed up exact matches — it also accelerates range queries (WHERE age > 30), sorting (ORDER BY), and prefix searches. (There's another structure, the LSM-tree, used by many NoSQL/write-heavy stores — compared in LSM-tree vs B-tree.)

What should you index?

Index the columns your queries actually filter, join, or sort on:

• Columns in WHERE clauses (the things you search by — email, username, status).
• Columns used in JOINs (foreign keys linking tables).
• Columns in ORDER BY (so the DB returns sorted results without re-sorting).

The primary key is always indexed automatically. Everything else is your choice, guided by the queries your app really runs.

Composite indexes and the left-most rule

🟠 You can index multiple columns together — a composite index, e.g. on (last_name, first_name). The catch is the left-most prefix rule: this index helps queries filtering on last_name, or on last_name + first_name — but not a query filtering on first_name alone, because the data is sorted by last name first (just like a phone book is useless for finding people by first name). Column order in a composite index is a real design decision, and knowing this rule is a classic senior signal.

The catch: indexes aren't free

🟠 If indexes are so great, why not index every column? Because every index has a cost:

So indexing is a trade: faster reads for slower writes and more storage. On a read-heavy table (most web apps), that's a great deal. On a write-heavy table, too many indexes hurt. The senior answer to "should we add an index?" is never a flat yes — it's "what do the queries look like, and is this table read-heavy or write-heavy?"

One pro move: the covering index

🔴 Normally the index finds where a row is, then the DB fetches the full row. But if an index contains all the columns a query needs, the database can answer entirely from the index without touching the table at all — a covering index. It's a powerful optimisation for hot queries, and dropping the term in an interview shows real depth.

How to actually check: EXPLAIN

Every SQL database has an EXPLAIN command that shows how a query will run — whether it's using an index or doing a dreaded full scan. Seeing "Seq Scan" on a big table is your cue to add an index; confirming "Index Scan" is how you prove it worked. Reasoning with EXPLAIN is the practical heart of database performance work.

What to read next

• Database Replication — copies for read capacity and failover
• Database Sharding — splitting data across machines
• SQL vs NoSQL — choosing the database itself
• ← The complete System Design guide (hub)

← SQL vs NoSQL · Database replication →