How Database Indexing Actually Works

A query that scans a million-row table without an index takes seconds. The same query with the right index takes milliseconds. Most developers know indexes are important but have a fuzzy idea of what they actually are under the hood. That fuzziness is why teams end up with indexes that do nothing, queries that ignore indexes they should use, and databases that slow to a crawl at scale.

What an Index Actually Is

An index is a separate data structure that the database maintains alongside your table. It holds a copy of one or more columns from your table, kept in sorted order, with pointers back to the full rows.

Think of it like the index at the back of a textbook. You want to find every page that mentions “B-tree.” You do not read the whole book. You go to the index, find “B-tree,” and it gives you the exact page numbers. Same idea. Instead of scanning every row in a table to find matches, the database checks the index and jumps directly to the rows it needs.

The tradeoff is that indexes cost something. Every time you insert, update, or delete a row, the database has to update every index on that table too. More indexes mean faster reads and slower writes. On a read-heavy table, that is fine. On a table that gets millions of inserts per second, index overhead matters.

How B-Tree Indexes Work

Nearly every index you have ever created is a B-tree index. PostgreSQL, MySQL, SQLite all use B-trees as the default.

A B-tree is a balanced tree where every node contains sorted keys and pointers to child nodes. The tree stays balanced, meaning every leaf node is the same distance from the root. That balance is what gives you O(log n) lookup time regardless of how many rows are in the table.

When you search for a value, the database starts at the root, compares your value to the keys at each node, and follows the right branch down until it reaches a leaf. A table with a billion rows has a B-tree about 30 levels deep. Thirty comparisons to find any row. That is why indexes are fast even at massive scale.

In practice, databases use a B+ tree variant where all actual data pointers live in the leaf nodes, and the leaf nodes are linked together in a chain.

That chain is what makes range queries fast. Once the database finds the start of your range, it just follows the leaf chain until it hits the end value without going back up the tree.

-- This uses the B-tree leaf chain for the range scan
SELECT * FROM orders WHERE created_at BETWEEN '2026-01-01' AND '2026-06-01';

Composite Indexes and the Leftmost Prefix Rule

A composite index covers multiple columns. This is where most developers hit unexpected behavior.

CREATE INDEX idx_city_lastname ON users (city, last_name);

This index can efficiently serve these queries:

-- Uses the index fully
SELECT * FROM users WHERE city = 'Bengaluru' AND last_name = 'Sharma';

-- Uses the index (city is the leftmost column)
SELECT * FROM users WHERE city = 'Bengaluru';

But it cannot efficiently serve this query:

-- Cannot use the index, city was skipped
SELECT * FROM users WHERE last_name = 'Sharma';

This is the leftmost prefix rule. A composite index on (A, B, C) can be used by queries filtering on A, or A and B, or A and B and C. Queries that skip the leftmost column and filter only on B or C cannot use the index and will do a full table scan instead.

Column order in a composite index matters as much as the columns themselves. Put the column you filter on most often first. If one column appears in almost every query and another appears less often, the frequent one goes first.

What Silently Breaks Your Indexes

These are the things that make a perfectly good index get ignored by the query planner. They rarely show up in code review.

Functions on indexed columns

-- Index on created_at exists, but this query ignores it
SELECT * FROM orders WHERE YEAR(created_at) = 2026;

-- This uses the index
SELECT * FROM orders WHERE created_at >= '2026-01-01' AND created_at < '2027-01-01';

When you wrap an indexed column in a function, the database cannot use the index because the index stores the raw column values, not the function output. Rewrite the condition to avoid the function on the column side.

Implicit type casting

-- user_id is an integer column, index exists
-- But passing a string forces a cast and the index is skipped
SELECT * FROM users WHERE user_id = '123';

Pass values of the matching type. This one is particularly common with ORMs that silently cast values.

Leading wildcards in LIKE

-- Index on username exists, but this cannot use it
SELECT * FROM users WHERE username LIKE '%john%';

-- This can use the index (wildcard only at the end)
SELECT * FROM users WHERE username LIKE 'john%';

A B-tree is sorted. A leading wildcard means the database does not know where in the sorted order to start looking, so it falls back to a full scan. If you need full-text search with leading wildcards, that is what full-text indexes are for.

Low cardinality columns

An index on a column like status that only has three possible values (active, inactive, deleted) is often not worth it. The database may decide a full table scan is cheaper than using the index, because the index would return a third of the table’s rows anyway. Indexes work best on high-cardinality columns where filtering narrows the result set significantly.

How to Know if Your Query Is Using an Index

EXPLAIN is your best tool. Run it before and after adding an index.

EXPLAIN ANALYZE SELECT * FROM orders WHERE user_id = 42;

Look for Index Scan or Index Only Scan in the output. If you see Seq Scan (sequential scan), your query is reading every row in the table. That is fine for small tables but a problem at scale.

EXPLAIN ANALYZE actually runs the query and shows real execution times. Use it in development, not production on expensive queries.

Covering Indexes

A covering index includes all the columns a query needs, so the database never has to touch the main table at all.

CREATE INDEX idx_covering ON orders (user_id, status, created_at);

-- This query can be answered entirely from the index
SELECT status, created_at FROM orders WHERE user_id = 42;

When the database can satisfy a query from the index alone, it is called an index-only scan. It is faster than a regular index scan because there is no second lookup into the table. For frequently run queries on large tables, a covering index can cut query time significantly.

When Not to Add an Index

Indexes are not free. Each one slows down writes because the database has to keep it in sync with the table. A table with fifteen indexes will have noticeably slower inserts and updates than the same table with three well-chosen indexes.

Do not add indexes to tables with fewer than a few thousand rows. Full table scans on small tables are fast and the overhead is not worth it.

Do not index every column. Index the columns that actually appear in your WHERE, JOIN, and ORDER BY clauses on slow queries. Measure first with EXPLAIN, then add the index, then measure again. If the query plan does not change, the index is not helping.

Drop indexes that are not being used. Most databases have a way to check index usage statistics. An index that never gets used is just slowing down your writes.

The One Thing to Take Away

An index trades write speed for read speed. B-trees give you O(log n) lookups by keeping values sorted in a balanced tree. Composite indexes follow the leftmost prefix rule, so column order is not arbitrary. And functions or type mismatches on indexed columns silently disable the index without any error. Know these three things and you will catch most indexing mistakes before they make it to production.