AlgoInsight

System Design

Database Indexes: A Detailed Guide

Indexes are how databases find data fast - but most people use them without knowing how they work. This is the mechanics: what an index is, the structures behind it, the types, and how to use them well.

By Admin2026-06-1815 min readdatabase-indexdatabasesb-treesystem-designperformancesql

A database index is the single most important tool for making queries fast - and one of the most commonly used without real understanding. People know "add an index to speed it up," but far fewer know what an index actually is, how it makes lookups fast, what structures power it, or which type to use when. This guide is the mechanics: a thorough, practical walk through how database indexes work, so you use them with understanding rather than superstition.

(For the trade-offs and the write cost of indexes at scale, see the companion piece on the hidden cost of indexes. This guide focuses on how they work.)

What an index is

A database index is a separate data structure that lets the database find rows quickly, without scanning the entire table. The classic analogy is the index at the back of a book: instead of reading every page to find mentions of a topic, you look it up in the index, which tells you exactly which pages to turn to. A database index does the same - it lets the database jump straight to the rows matching a query instead of reading every row.

Concretely, an index stores a sorted copy of one or more columns, along with pointers back to the full rows in the table. Because the index is sorted, the database can search it efficiently (much faster than scanning unsorted data) and then follow the pointers to the actual rows.

Without an index, finding rows matching a condition requires a full table scan - reading every row to check whether it matches. For a large table, that's slow. With an index on the relevant column, the database uses the sorted index to locate matching rows quickly. That's the entire purpose: turn a slow full scan into a fast lookup.

graph LR
    Q["Query: WHERE email = 'x'"] --> CHK{Index on email?}
    CHK -->|No| SCAN[Full table scan:<br/>read every row]
    CHK -->|Yes| IDX[Search sorted index →<br/>jump to matching rows]
    SCAN --> SLOW[Slow on large tables]
    IDX --> FAST[Fast - logarithmic lookup]

This diagram shows what an index does. For a query filtering on email, the database checks whether an index exists on the email column. Without one, it must do a full table scan, reading every row, which is slow on large tables. With an index, it searches the sorted index structure and jumps straight to the matching rows, which is fast - a logarithmic lookup instead of a linear scan.

The structure behind most indexes: the B-tree

Most database indexes are built on a structure called a B-tree (or its variant, the B+ tree). Understanding it at a high level explains why indexes are fast.

A B-tree is a balanced tree structure that keeps data sorted and allows searches, insertions, and deletions in logarithmic time. "Logarithmic" is the key: in a balanced tree, finding any value takes a number of steps proportional to the height of the tree, which grows very slowly as data grows. A B-tree over a million rows might be only a few levels deep, so finding any row takes only a few steps - instead of potentially a million steps for a full scan. Over a billion rows, it's still only a handful of levels. This is why an index can find a row in a huge table almost instantly: the search cost grows logarithmically, not linearly, with the data.

The tree stays balanced as data is inserted and deleted, which guarantees that lookups stay fast - no part of the tree becomes much deeper than another. This balancing is part of what makes maintaining an index cost something on writes (the tree must be kept balanced as rows change), but it's also what guarantees consistently fast lookups.

B-trees are the default for a reason: they handle not just exact-match lookups but also range queries efficiently (find all values between X and Y), because the sorted structure keeps nearby values together. This versatility makes them the workhorse index type.

Common types of indexes

Beyond the standard B-tree index, databases offer several index types for different needs:

Choosing the right type matters: a hash index is faster for pure equality but useless for ranges; a composite index serves multi-column queries that single-column indexes can't.

The primary index and clustered vs. non-clustered

A couple of important concepts about how indexes relate to the table's physical storage:

The primary key of a table is automatically indexed - it's the main way rows are identified and looked up. Beyond that, indexes come in two physical flavors:

Understanding this explains why lookups by primary key are often fastest (it's typically the clustered index, so the data is right there in order) and why additional indexes are separate structures with their own cost.

Index selectivity: when an index helps

Not every index is worth having, and the concept that explains why is selectivity - how many distinct values a column has relative to the number of rows. An index is most effective on a highly selective column, where each value matches very few rows (like a unique email or user ID). Looking up such a value, the index narrows to one or a handful of rows instantly.

An index on a low-selectivity column - one with few distinct values, where each matches a huge fraction of the rows - is far less useful. The classic example is a boolean or status column with only two or three possible values: an index on it, when queried, still points to a huge portion of the table, so the database may decide a full scan is just as fast and skip the index entirely. This is why indexing a column like "active/inactive" often does little good. Understanding selectivity tells you which columns are worth indexing: the ones where a lookup meaningfully narrows the result, not the ones where every value matches half the table.

Covering indexes: answering a query from the index alone

A powerful, more advanced concept: a covering index contains all the columns a query needs, so the database can answer the query entirely from the index without touching the table. Normally an index gets you to the right rows, and then the database fetches those rows from the table to read the other columns. But if the index already includes every column the query references, that second step is skipped - the query is served straight from the index, which is faster.

For example, if a query selects a user's name by their email, an index on (email, name) "covers" it - the index has both columns, so the database reads the answer from the index alone. Covering indexes are a real optimization for hot queries, though they make the index larger (storing more columns) and thus cost a bit more on writes and storage - the same trade-off as always, applied to a more capable index.

How the database decides whether to use an index

A subtlety that surprises people: just because an index exists doesn't mean the database will use it. Databases have a query optimizer that estimates the cost of different ways to execute a query and picks the cheapest. For a given query, it weighs using an index against scanning the table - and sometimes chooses the scan, because for that query (especially on a low-selectivity column, or one expected to match most rows) a scan is genuinely faster than an index lookup followed by many row fetches.

This is why the query plan (EXPLAIN) matters so much: it shows what the optimizer actually decided. An index you added might be ignored because the optimizer judged a scan cheaper, or because the query was written in a way that prevents the index from being used (applying a function to the indexed column, for instance, can stop the database from using the index on it). Understanding that the optimizer chooses - and that your job is to give it useful indexes and write queries that can use them - separates someone who adds indexes hopefully from someone who makes them reliably effective. The index is necessary but not sufficient; the query has to be written so the index applies, and the optimizer has to judge it worthwhile.

Maintaining indexes over time

Indexes aren't set-and-forget. Over a database's life:

Good indexing is an ongoing practice, not a one-time setup - the right indexes are the ones that match how the data is actually being queried right now.

How to use indexes well

Practical principles for indexing effectively:

-- See whether a query uses an index or scans the whole table
EXPLAIN SELECT * FROM users WHERE email = 'someone@example.com';

-- Create an index to speed up that lookup
CREATE INDEX idx_users_email ON users(email);

-- A composite index for a multi-column query
CREATE INDEX idx_orders_customer_date ON orders(customer_id, order_date);

The EXPLAIN command is your most important tool here: it tells you the truth about whether the database is using your index or scanning the table, which turns indexing from guesswork into something you can verify.

Tip: Emeka's note from production: The single most useful habit I can give you is to read the query plan. Engineers add an index, assume it's working, and move on - but the database doesn't always use the index you expect, for reasons ranging from how the query is written to the database's own cost estimates. EXPLAIN (or your database's equivalent) shows you what's actually happening: is it using the index, or scanning millions of rows anyway? Half the "my query is still slow despite the index" problems I've helped debug came down to an index that existed but wasn't being used, which the query plan revealed in seconds. Don't assume - check the plan.

Interview: Understanding indexes is fundamental for system design and database questions. Beyond "add an index to speed up the query," demonstrating that you know an index is a sorted structure (usually a B-tree) enabling logarithmic lookups, that composite indexes serve multi-column queries, and that you'd verify usage with a query plan - that's the depth that signals real database competence. And pairing it with the trade-off (indexes cost write performance) shows you understand indexes as an engineering decision, not a free button.

The bottom line

A database index is a separate sorted data structure that lets the database find rows fast - jumping to matching rows instead of scanning the whole table. Most indexes are B-trees, which give logarithmic lookup time, so even a huge table is searchable in a few steps, and they handle both exact-match and range queries. Index types (B-tree, hash, composite, unique, full-text, specialized) suit different needs, and clustered versus non-clustered describes how an index relates to the table's physical storage. Used well - indexing the columns your real queries touch, getting composite column order right, not over-indexing, and verifying with the query plan - indexes are the most powerful tool you have for fast queries.

Know how they work, and you use them with intent rather than superstition. For the cost side of the equation - why you don't just index everything - see the companion guide on the hidden cost of indexes. We cover database performance and indexing across System Design Fundamentals.

Go deeper

More articles