How does Database Indexing work?

"How does database indexing work?" is one of the most common questions in a system design or backend interview, and the answer separates people who memorized "it makes queries faster" from people who can explain the mechanism. A strong answer builds from the problem to the data structure to the trade-off - and then handles the follow-up almost everyone gets: "how is it different in NoSQL?" Here is how to answer the whole thing, and actually understand it.

Interviewer: How does indexing work in a database?

Do not start with "it speeds up queries." Start with why it needs to. (Indexing sits alongside caching, replication, and sharding as a core database building block - and it is usually the first one you reach for.)

Start with the problem: the full scan

Without an index, finding rows means a full table scan - the database reads every row and checks your condition. Looking for WHERE email = 'a@b.com' in a ten-million-row table reads ten million rows to find one. That is O(n), and it gets linearly worse as the table grows.

The book analogy lands well in an interview: finding every mention of a word by reading the book cover to cover is a scan. The index at the back - terms in sorted order, each pointing to page numbers - lets you jump straight there. A database index is exactly that idea.

The core idea: a sorted copy with pointers

An index is a separate data structure that stores the indexed column(s) in sorted order, each entry pointing back to the full row. Because it is sorted, you no longer scan - you search. The database can binary-search the sorted keys to find a value in O(log n) instead of O(n). That single sentence - "a sorted copy of the column plus a pointer to the row" - is the heart of the answer.

How it is actually stored: the B-tree

Now name the structure, because the interviewer wants to know you know it. Almost every relational index is a B-tree (specifically a B+ tree): a balanced tree kept in sorted order, shallow and wide, so walking from the root to a leaf is a handful of steps - O(log n) - even for billions of rows.

Two properties of the B-tree explain what indexes are good at:

• The nodes are sorted, so equality lookups (= 'a@b.com') and range scans (BETWEEN, <, >) both work - you seek to the start and walk.
• The leaves are linked in order, so ORDER BY, MIN, and MAX come almost for free - the data is already in order.

Contrast it with a hash index, which maps a key straight to a location in O(1) - faster for exact equality, but useless for ranges or sorting because a hash destroys order. That contrast is a good thing to volunteer: the reason B-trees are the default is that they serve equality and range and sort, where a hash only does equality.

What gets compared at each node

Here is the question people actually have, using an index on email: when you look up mike@x.co, does the tree compare the whole email at each node, or one character per level? The whole value. Each B-tree node stores a few complete keys (whole emails), kept in sorted order, and acts as a signpost. At a node you compare your entire search value against those sorted keys to decide which child pointer to follow - "is mike@x.co before dave@x.co, between dave@x.co and rosa@x.co, or after rosa@x.co?" - then descend to that child and repeat, until you reach the leaf that holds the exact key and its pointer to the row:

The comparison between two full keys is of course done character by character (strings sort lexicographically, so mike vs mila is decided at the third character) - but that is just how two whole values are ordered. The unit of comparison is the entire email, and the tree's depth is about log(n) levels for n rows, completely independent of how long the email string is.

That distinction matters because there is a structure where each level is one character - a trie (or radix tree) - and it is a different data structure that SQL B-tree indexes do not use:

So the lookup, end to end:

1. Start at the root, compare your whole value against its sorted keys, follow the child pointer for the range you fall into.
2. Repeat down each level - a handful of comparisons total - until you reach the leaf holding the exact key.
3. The leaf entry points to the row; follow it to read the full record.

If the index contains every column the query needs (a covering index), step 3 is skipped - the answer is read straight from the leaf, never touching the table. That "index-only scan" is the fastest case.

Clustered vs secondary: where the row actually lives

This is the detail that shows depth. There are two flavors of index, and the difference is where the row data sits:

• A clustered index stores the table's rows in the index's sorted order - the leaves are the table. There is one per table (the data can only be sorted one way); in MySQL's InnoDB the primary key is the clustered index. A lookup by that key lands directly on the row.
• A secondary (non-clustered) index is a separate structure whose leaves hold the indexed value plus a pointer to where the row really is - the primary key (InnoDB) or a physical row location (PostgreSQL's heap). A lookup by a secondary index finds the pointer, then does a second hop to fetch the row.

That second hop is exactly why covering indexes matter, and why a secondary-index lookup can be a touch slower than a clustered one.

The trade-off (the interviewer will push here)

End the "how" with the cost, because the natural next question is "so why not index everything?"

• Reads get faster, writes get slower. Every INSERT, UPDATE, and DELETE must also update every index on the table, in sorted position. Ten indexes means a write does eleven pieces of work.
• Indexes cost storage (they are copies) and memory (they compete for cache).
• So you index the columns queries actually filter, join, and sort on, and skip low-selectivity columns (a boolean flag the optimizer will ignore anyway).

A clean answer is: an index trades write speed and space for read speed, so you add them deliberately, for measured slow queries, not everywhere. When indexes start taxing writes too heavily, one architectural answer is to keep a separate, heavily-indexed read store fed from the write store - the idea behind CQRS. If you want the deeper treatment of building the right index (composite column order, covering indexes, when it stops helping), that is a topic of its own; here, the mechanism is the point.

The follow-up: how indexing differs in SQL vs NoSQL

This is where a lot of candidates fall down, and it is the second half the interviewer is really after.

In a relational database, indexing is flexible and the database's job. The data lives on one logical node with a global B-tree available over any column. You can add a secondary index on any column at any time, and the query planner will automatically use it. ACID transactions keep every index perfectly consistent with the table on every write. You model your data first and query it many ways later - the indexes make that cheap.

In NoSQL, the index model is shaped by the fact that data is partitioned across many nodes for scale, and that changes everything:

• The primary access path is the partition key. Data is physically placed by hashing (or ranging) the partition key, so the only naturally fast query is "give me the item(s) for this key." There is no single global B-tree spanning the whole dataset - each node holds and indexes only its own slice.
• Secondary indexes are limited and costly. In DynamoDB, a Global Secondary Index is a second copy of the data under a different key, maintained asynchronously - so it is eventually consistent (reads can be stale), it burns extra write capacity on every base-table write, and you cannot make it strongly consistent. In Cassandra, a native secondary index is local to each node, so a query on it must fan out to every node in the cluster (a scatter-gather) and scales poorly - which is why the standard advice is to avoid it and instead create a second table keyed for that query.
• You design for queries, not data. Because you cannot cheaply "add an index and query however," NoSQL forces query-first modeling: enumerate your access patterns up front and build a table or index per pattern. Discover a new query later and you often need a new table plus a backfill of all existing data.
• No ad-hoc joins, and index updates lag, so a write is not instantly visible through its secondary index.

The reason for the difference is the whole point: a relational database optimizes a single node for flexible querying, using a global index over any column; a NoSQL store distributes data by key across nodes for horizontal scale, which makes a global secondary index expensive to maintain - so it trades query flexibility for write and storage scale. Say that, and you have answered the real question.

	SQL (relational)	NoSQL (partitioned)
Primary access	Any column via a B-tree	The partition key
Secondary index	Add on any column, anytime	Limited, often eventually consistent
Consistency of index	Kept in sync (ACID)	Often async / eventually consistent
Add a new query later	Just add an index	Often a new table + backfill
Cross-node global index	N/A (single logical node)	Expensive; usually avoided
Best when	You slice data many ways	Access patterns are few and key-shaped

How to deliver the answer

Structure it and you sound senior: the problem (a scan is O(n)) -> the idea (a sorted copy with pointers) -> the structure (a B-tree, O(log n), good at equality/range/sort) -> the execution (root to leaf to row; covering skips the last hop) -> the trade-off (faster reads, slower writes, so index deliberately) -> the SQL vs NoSQL difference (flexible global index vs partition-key-first, because of distribution). That arc is what a strong answer to "how does indexing work" looks like - the mechanism, the cost, and the awareness that the answer changes once data is spread across nodes.