Grokking Database Indexing: The Secret Behind Blazing-Fast Queries

This blog explores the internal workings of database indexes, focusing on how structures like B-trees enable fast data retrieval. It explains how indexes optimize query performance, the trade-offs involved, and why understanding index internals is crucial for designing efficient, scalable systems.

Imagine running a query on a massive database table and getting results in milliseconds.

How is that possible?

For many developers, the answer comes as an epiphany the first time they add an index to a slow query – a report or API call that was taking 5-6 seconds suddenly runs in under a second after indexing the right column.

It may feel like magic, but there’s no sorcery involved – just clever use of data structures.

Let's explore the internals of database indexes to understand how they make data retrieval so fast (and even when not to use them!).

What Is a Database Index?

A database index is essentially an auxiliary data structure that helps the database find information without scanning every row (like the index of a book saves you from reading every page).

In practical terms, an index stores a sorted copy of certain column values along with pointers to the full rows.

This way, the database can search the smaller index instead of the entire table, drastically reducing the work needed to find the data.

How Indexes Speed Up Queries

Let’s dive a bit deeper into how an index makes queries faster.

Without an index, if you search for WHERE name = 'Alice' on a large table, the database might have to inspect every row until it finds all the Alices – this is akin to reading a whole phone book to find one name.

That approach is O(N) in computational terms (meaning time grows linearly with number of rows).

Now enter the index: with an index on the name column, the database can use a much more efficient strategy, roughly O(log N), by doing something like a binary search on the sorted index data.

In essence, the index lets the database skip over huge swaths of data that don’t matter to your query, homing in only on the relevant portions.

Here’s what happens under the hood when you query a table using an indexed column:

1. Index lookup: The database checks the index (sorted by the target field) instead of scanning the entire table.

2. Traverse the tree: It follows the index’s B-tree pointers from root to leaf, quickly narrowing down to the matching entries with just a few comparisons.

3. Retrieve the row: Once the index finds the right key, it uses the stored pointer to fetch the full row from the main table.

A well-chosen index can turn a brute-force scan into a surgical lookup, saving a ton of time. It’s worth noting that under the hood, the index is often maintained as a sorted “pseudo-table” with just the indexed column and a reference to the full row.

So when you CREATE INDEX on most_recent_activity in a table, the database builds a structure sorted by most_recent_activity containing values and pointers to each corresponding row.

This sorted order is the secret sauce that enables efficient binary search-like behavior.