Database Indexing: How the Right Index Turns a Table Scan into a Log-N Lookup
How database indexes work, why B+trees dominate, and how to choose composite, covering, partial, and LSM indexes without wrecking write throughput.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
A query that takes 4 seconds on a 500-million-row table and 3 milliseconds after you add one index is not a different query — it's the same query with a different way of finding rows. Indexing is the single highest-leverage lever in database performance, and it shows up in almost every system design interview the moment your data outgrows a full scan.
The catch is that an index is not free. Every index you add is a second data structure the database must keep in sync on every write, and it eats memory that would otherwise cache your actual table. The skill is not "add indexes" — it's knowing exactly which index answers which query, and what you pay for it.
What an index actually is
An index is an auxiliary data structure that maps column values to the physical locations of matching rows. Without one, answering WHERE email = 'ana@x.com' means reading every page of the table — an O(N) sequential scan. With a B+tree index on email, the database descends a balanced tree and lands on the row in O(log N) steps.
Put concrete numbers on it. A 500M-row table with a B+tree of fan-out ~500 is only about four levels deep, because 500⁴ ≈ 62 billion. So a point lookup touches roughly 4 index pages instead of scanning millions of table pages. That is the entire pitch: turn a linear scan into a handful of page reads.
The cost is write amplification. Every INSERT, UPDATE, or DELETE must maintain every index that covers an affected column. Ten indexes means a single insert does eleven writes — one to the table, ten to the indexes. Indexes also consume buffer-pool memory that would otherwise cache hot table pages, so over-indexing can slow down even a read-heavy workload by starving the cache. Every index is a bet that its read speedup outweighs this standing write-and-memory tax.
Why B+trees beat hash indexes as the default
Two structures dominate index implementations, and the choice hinges on one question: do you ever need ranges?
| Property | B+tree | Hash index |
|---|---|---|
| Point lookup | O(log N) | O(1) average |
Range scan (>, <, BETWEEN) | Yes, walk linked leaves | No |
ORDER BY for free | Yes (leaves are sorted) | No |
Prefix / LIKE 'ab%' | Yes | No |
| Behavior under collisions | Stays balanced | Degrades |
A B+tree keeps keys sorted in a balanced tree whose leaf nodes are linked together. That linked, sorted leaf layer is what makes it the workhorse: once you find the start of a range you just walk sideways through the leaves, so created_at BETWEEN x AND y and ORDER BY created_at come nearly free.
A hash index gives faster O(1) equality lookups, but it stores keys by hash — there is no order — so it cannot serve ranges, sorting, or prefix matches, and it degrades on collisions. Reach for a hash index only for equality-only access on high-cardinality keys (Postgres hash indexes, Redis, in-memory tables). For everything else, the B+tree is the default precisely because it is the only one that also handles BETWEEN, <, >, and ORDER BY.
Clustered vs. non-clustered: where the row lives
The most consequential distinction is where the actual row data sits relative to the index.
A clustered index stores the full rows in the leaves of the B+tree, physically sorted by the index key. The table is the index. InnoDB's primary key and SQL Server clustered indexes work this way, so a primary-key lookup fetches the row in a single tree descent.
A non-clustered (secondary) index stores only the key plus a pointer to the row. What that pointer is matters. In Postgres it's a physical tuple ID into the heap. In InnoDB it's the primary-key value — which means a secondary-index lookup does two B+tree traversals: one through the secondary index to find the primary key, then one through the clustered index to fetch the row.
-- InnoDB: this can cost two B+tree descents
SELECT * FROM users WHERE email = 'ana@x.com';
-- 1) walk the email index -> get primary key (user_id)
-- 2) walk the clustered PK index -> fetch the full rowThat hidden second hop is the motivation for the next tool.
What is a covering index?
A covering index contains every column a query references — in SELECT, WHERE, and ORDER BY — so the database answers the whole query from index pages alone. Postgres calls this an index-only scan. It skips the per-row heap/table fetch entirely, and in random-I/O workloads that heap fetch is frequently the dominant cost.
You build one by carrying payload columns that don't need to be sorted. In Postgres and SQL Server, INCLUDE appends them to the leaf pages without adding them to the B+tree's sortable key:
-- Serves "SELECT status FROM orders WHERE user_id = ?" with zero heap reads
CREATE INDEX idx_orders_user ON orders (user_id) INCLUDE (status);Now the query about a user's order statuses never touches the table — it reads only the index. The trade-off is a fatter index that costs more to store and maintain, so you cover the specific hot queries that need it, not every query.
Composite indexes and the left-prefix rule
A composite index on (a, b, c) is ordered lexicographically — first by a, then b, then c — exactly like a phone book sorted by last name, then first name. That ordering dictates which queries it can serve. The rule: an index helps only when the query uses a left prefix of the key.
| Query | Uses (a, b, c)? |
|---|---|
WHERE a = ? | Yes — leading column |
WHERE a = ? AND b = ? | Yes — full prefix |
WHERE a = ? AND b = ? AND c = ? | Yes — whole key |
WHERE a = ? AND c = ? | Partly — uses a, then filters c |
WHERE b = ? | No — no leading a |
A second rule bites often: a range predicate stops the index at that column. WHERE a = ? AND b > ? AND c = ? can use (a, b) to seek, but c becomes a filter, not a seek, because once you're scanning a range of b the c values are no longer in sorted order. The design consequence is concrete — put high-selectivity equality predicates first and range predicates last when you choose column order.
When the query is still slow: a worked design
Take a real bottleneck. A 500M-row orders table, and this query is slow:
SELECT * FROM orders
WHERE status = 'PENDING'
AND created_at > now() - interval '1 day';Walk it the way you would in an interview:
- Check selectivity first.
'SHIPPED'might be 95% of rows while'PENDING'is 0.5%. Postgres will refuse a plain index onstatusfor common values because scanning the index plus fetching that many rows is slower than a sequential scan. So an index only helps for the selective values. - Composite, ordered right.
CREATE INDEX ON orders (status, created_at DESC)clusters each status together and keeps its rows time-ordered. The query becomes an index range scan: seek toPENDING, walk backward from the newest row for one day, stop. - Partial index — the real win. Because you only ever query
PENDING, store only those rows:
CREATE INDEX idx_pending_recent ON orders (created_at DESC)
WHERE status = 'PENDING';This shrinks the index 50–100x versus indexing all statuses, slashing its maintenance cost, and it self-cleans: when an order flips from PENDING to SHIPPED, its entry drops out automatically. For an append-only table, pair it with monthly partitioning on created_at so aged-out partitions can be dropped in one cheap metadata operation instead of a mass DELETE.
Why write-heavy systems reach for LSM-trees
B+trees do in-place updates — every write dirties a page that must eventually flush as a random I/O. On SSDs that means write amplification and pain under write-heavy load. That's why Cassandra, RocksDB, LevelDB, and ScyllaDB use LSM-trees instead.
An LSM-tree buffers writes in an in-memory memtable, flushes them to disk as immutable sorted files (SSTables) using cheap sequential writes, and merges those files in the background via compaction. The trade is read amplification: a read may have to check several SSTables, which is why LSM engines lean on bloom filters to skip files that definitely don't hold the key. Immutable, densely packed SSTables also compress far better than a B+tree's half-full pages.
| Dimension | B+tree | LSM-tree |
|---|---|---|
| Writes | In-place, random I/O | Sequential, buffered |
| Write throughput | Lower | Higher |
| Read amplification | Low | Higher (mitigated by bloom filters) |
| Best for | Read-heavy, range-scan-heavy | Write-heavy, time-series |
Neither wins outright. LSM shines for write-heavy and time-series ingestion; B+trees shine for read-heavy, range-scan-heavy workloads. And for one specialized case — low-cardinality columns in read-mostly warehouses — a bitmap index stores one bit per row per distinct value and answers WHERE gender='F' AND country='IN' with fast bitwise AND/OR over billions of rows. It's rare in OLTP because every row update contends on shared bitmap pages, effectively serializing writes.
How this shows up in interviews
Indexing is where a system design interview stops being hand-wavy and starts testing whether you've actually run a slow query. Interviewers probe it in a predictable arc: you propose a schema, they hand you a slow query, and they watch whether you reason about selectivity and column order rather than reflexively "adding an index."
The strong signals are specific. You mention that each index taxes writes, so you don't index everything. You order a composite index by putting equality columns before range columns and cite the left-prefix rule. You reach for a partial or covering index when the access pattern is narrow. And when the workload is write-heavy or time-series, you name LSM-trees and explain the write-vs-read amplification trade instead of assuming every database is a B+tree. Getting the why right — sequential vs. random I/O, one tree descent vs. two — is what separates a memorized answer from an engineered one.
Further learning
- SQL Index: Indexes in SQL, Database Index — Socratica's clear primer on what an index is and how lookups change.
- Database Indexing Demystified — ByteByteGo's visual deep dive into index structures and trade-offs.
Indexing rarely stands alone in a design. It sits next to Scaling when a single node can't hold the working set, informs the SQL vs NoSQL choice through the B+tree-vs-LSM split, interacts with the CAP Theorem once indexes must stay consistent across replicas, and pairs with Caching as the next layer when even index lookups aren't fast enough. You can also practice this topic on YeetCode to lock in the trade-offs.
FAQ
Does adding more indexes always make a database faster?
No — indexes speed up reads but tax every write. Each INSERT, UPDATE, or DELETE must update every index covering the affected columns, so ten indexes turn one row change into eleven writes. Indexes also occupy buffer-pool memory that would otherwise cache table pages, meaning an over-indexed table can serve reads slower because its hot data no longer fits in cache. Index deliberately: cover the queries that are actually slow and hot, and drop indexes nothing queries.
When should I use a hash index instead of a B+tree?
Only when you do pure equality lookups on a high-cardinality column and never need ranges, sorting, or prefix matches. A hash index gives O(1) average point lookups versus a B+tree's O(log N), but it stores keys unordered, so it cannot serve BETWEEN, <, >, ORDER BY, or LIKE 'ab%', and it degrades on hash collisions. Because most real workloads eventually need one of those ordered operations, the B+tree is the safe default and hash indexes stay a niche optimization (Postgres hash indexes, Redis, in-memory tables).
Why does a composite index on (a, b) not help a query that filters only on b?
Because a composite index is sorted lexicographically — first by a, then by b — so the b values are only ordered within each a group, never globally. A query filtering on b alone has no way to seek, since the matching rows are scattered across every a bucket. This is the left-prefix rule: the index serves a query only if it uses a leading prefix of the key columns. To make WHERE b = ? fast you need a separate index that leads with b.
What is the difference between a covering index and a normal index?
A normal index stores the key and a pointer back to the row, so the database still fetches the full row from the table (a heap lookup) to read columns the index doesn't hold. A covering index contains every column the query touches, so the database answers entirely from index pages in an index-only scan, skipping the heap fetch that often dominates cost in random-I/O workloads. You build one by adding payload columns with INCLUDE, which keeps them at the leaves without bloating the sortable part of the B+tree.
Why do write-heavy databases like Cassandra use LSM-trees instead of B+trees?
Because B+trees update pages in place, and in-place updates are random I/O that amplifies writes on SSDs. An LSM-tree instead buffers writes in memory and flushes them as immutable sorted files using cheap sequential writes, then compacts those files in the background. That gives dramatically higher write throughput and better compression, at the cost of read amplification — a read may scan several files — which bloom filters largely hide. The result: LSM-trees win for write-heavy and time-series workloads, while B+trees remain better for read-heavy, range-scan-heavy access.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.