How a Database Index Makes Queries 1000x Faster

The short answer

Quick answer: Without an index, a database must read every row in a table to find the ones you asked for. That is a full table scan. An index is a separate, sorted data structure, usually a B-tree, that maps column values to the location of their rows. Because it is sorted and shaped like a shallow tree, the database can find any value in a handful of steps, even among hundreds of millions of rows. The trade-off is that every index takes disk space and must be updated on every write.

The book analogy

To find every mention of "replication" in a 900-page textbook, you could read all 900 pages. Or you could turn to the index at the back, find "replication" in the alphabetical list, and go straight to pages 212, 340 and 588.

A database index is the same thing: a sorted list of values, each pointing to where the full row lives.

Why the difference is so large

Take a table with 100 million rows and this query:

SELECT * FROM users WHERE email = '[email protected]';

• Without an index: the database reads all 100 million rows and checks each email. That is gigabytes of data.
• With an index on email: it walks a B-tree about four levels deep, reading roughly four pages, then fetches one row.

That is the difference between seconds or minutes and well under a millisecond. The headline "1000x" is, if anything, modest for large tables.

How a B-tree works

A B-tree is a balanced tree designed for storage that is read in pages:

• Each node is one disk page (commonly 8 KB) and holds many sorted keys, often hundreds.
• Internal nodes hold keys and pointers to child nodes: "values below 5000 are down this branch".
• Leaf nodes hold the indexed values and pointers to the table rows. Leaves are linked to their neighbours.

Because each node branches hundreds of ways, the tree stays very shallow. With a few hundred keys per node, three levels cover millions of rows and four levels cover hundreds of millions or more. A lookup reads one page per level.

The sorted, linked leaves give B-trees a second ability: range scans. For WHERE created_at BETWEEN '2026-01-01' AND '2026-01-31', the database finds the first matching entry and walks along the leaves until it passes the end. The same structure serves:

• Equality: =
• Ranges: <, >, BETWEEN
• Prefix matches: LIKE 'abc%'
• Sorting: ORDER BY on the indexed column, with no separate sort step

A hash map would be marginally faster for exact matches but cannot do any of the others, which is why B-trees are the default almost everywhere.

Indexes are not free

A table with ten indexes does ten extra tree updates per insert. Index what your queries need, and remove indexes that are never used.

Composite indexes and column order

An index can cover several columns:

CREATE INDEX idx_orders_customer_date ON orders (customer_id, created_at);

It is sorted by customer_id first, then by created_at within each customer, like a phone book sorted by surname and then first name. That makes it useful for:

• WHERE customer_id = 42
• WHERE customer_id = 42 AND created_at > '2026-01-01'
• WHERE customer_id = 42 ORDER BY created_at DESC

But not for WHERE created_at > '2026-01-01' on its own, just as a phone book is no help for finding everyone named "Sam" regardless of surname. This is the leftmost prefix rule.

A good rule of thumb for ordering columns: equality conditions first, then the range or sort column.

Covering indexes

Normally the index finds the row's location and the database then fetches the row from the table. If the index already contains every column the query needs, that second step can be skipped. This is an index-only scan, and the index is said to cover the query.

CREATE INDEX idx_users_email_name ON users (email) INCLUDE (name);
SELECT name FROM users WHERE email = '[email protected]';

Clustered vs secondary indexes

In some databases the table itself is stored as a B-tree ordered by the primary key. MySQL's InnoDB works this way; the primary key is a clustered index, and every secondary index stores the primary key as its row pointer. PostgreSQL stores rows in an unordered heap, and all indexes point into it. The practical upshot: in InnoDB, primary key lookups are especially fast and a wide primary key bloats every other index.

Why your index might be ignored

The planner uses an index only when it estimates that will be cheaper. Common reasons it does not:

• Low selectivity. If a condition matches a large share of the table (say status = 'active' on 90% of rows), a sequential scan is faster than millions of scattered index lookups.
• A function on the column. WHERE lower(email) = '...' cannot use a plain index on email. Create an expression index on lower(email).
• A leading wildcard. LIKE '%son' cannot use a B-tree, because the start of the value is unknown.
• Type mismatch. Comparing a text column to a number forces a conversion on every row.
• Wrong column order in a composite index.
• Stale statistics, so the planner misjudges how many rows match.

Always check with EXPLAIN:

EXPLAIN ANALYZE SELECT * FROM orders WHERE customer_id = 42;

Look for "Index Scan" versus "Seq Scan". Markus Winand's free book Use The Index, Luke is the best practical guide to reading these.

What to index

1. Primary keys (indexed automatically).
2. Foreign keys used in joins. Missing these is a common cause of slow joins and of the N+1 query problem hurting more than it should.
3. Columns in frequent WHERE, JOIN and ORDER BY clauses.
4. Columns that must be unique, with a unique index.

Avoid indexing columns with very few distinct values on their own, and tiny tables where a scan is already instant.

Other index types

The PostgreSQL indexes documentation describes each in detail.

Frequently asked questions

Do indexes slow down inserts?

Yes. Each index must be updated on every insert, and on updates and deletes that touch its columns. The more indexes, the slower the writes.

Should I index every column?

No. Unused indexes waste space and slow writes. Add indexes for real, measured query patterns.

What is the difference between a primary key and an index?

A primary key is a constraint: unique and not null. Databases enforce it by creating an index automatically.

How do I know whether a query uses an index?

Run it with EXPLAIN (or EXPLAIN ANALYZE) and read the plan.

Conclusion

An index trades write speed and disk space for dramatically faster reads. The B-tree's sorted, shallow structure turns a search through millions of rows into a few page reads, and supports ranges and sorting too. Index the columns you filter, join and sort on, put composite columns in the right order, and let EXPLAIN confirm that the database agrees with you.

Related articles

• B-Trees vs LSM Trees: Why Databases Store Data Differently
• How Query Planners Decide the Fastest Way to Run Your SQL
• What Is the N+1 Query Problem and How to Fix It
• How Hash Maps Achieve O(1) Lookups
• How Google Search Returns Results in Milliseconds

Sources and further reading

• Indexes, PostgreSQL documentation
• Use The Index, Luke
• B-tree (Wikipedia)