Database Indexing Explained: B-Trees, LSM Trees & Column Order

Every slow-query story ends the same way: someone adds an index, the p99 drops by three orders of magnitude, and the incident closes. That half is easy. The interview question is the other half — what did the index cost, why does the query planner sometimes refuse to use the one you added, and why did the table with nine indexes on it fall over on writes while the queries were fine.

This post builds indexing from the page reads up: the arithmetic that makes a B-tree three levels deep, what each additional index costs on every insert, why composite column order is the actual design decision, when the planner is right to ignore you, how LSM trees make the opposite trade, and the problems an index cannot touch.

What an index buys, in page reads

Take a tickets table: 50 million rows, about 200 bytes each, so roughly 10 GB on disk. You want one row by id.

Without an index the database reads the whole table. At 1 GB/s off a decent NVMe drive that is 10 seconds of sequential I/O, plus the CPU to evaluate the predicate against 50 million rows.

With a B-tree index it reads four 8 KB pages — three to walk down the tree, one to fetch the row. Each random read on the same drive costs on the order of 100 microseconds, so 0.4 milliseconds. The ratio is about 25,000x.

That is the entire pitch, and it is worth stating in page reads rather than seconds — page reads are what the planner compares when it decides whether to use your index.

The B-tree, and why it is only ever three or four levels deep

Almost every index in a relational database is a B+tree: a sorted, balanced tree where the internal pages hold only separator keys and child pointers, and every actual index entry lives in a leaf page at the bottom.

The number that makes it work is fanout — how many children one internal page can point to. With Postgres's 8 KB page and a bigint key, an entry is an 8-byte key plus a pointer, call it 16 bytes. So one page holds roughly 8192 / 16 ≈ 500 entries.

Compound that:

• 1 level: 500 keys
• 2 levels: 500² = 250,000
• 3 levels: 500³ = 125,000,000
• 4 levels: 500⁴ = 62,500,000,000

A three-level B-tree indexes 125 million rows. Four levels covers 62 billion. This is why depth is never what you tune: no table you will be asked about has an index more than four or five levels deep, and the top two levels are almost always in memory, so a "four page read" lookup is usually one or two real trips to disk.

The linked leaves are the under-appreciated half. A hash index answers = in one probe and cannot answer > or ORDER BY at all. The B-tree's sort order is what makes it the default, and it is also what makes column order matter later on.

Every index is a tax on writes

This is the part most candidates cannot quantify, and it is where the good follow-up questions live.

An index is a second copy of some of your columns, kept sorted. Keeping it sorted is not free. When you insert one row into a table with five secondary indexes, the database must descend six B-trees and dirty at least six pages. Those are 8 KB pages, for a 200-byte row:

6 pages x 8 KB = 48 KB of page writes for 200 bytes of data  ->  ~245x

At 2,000 inserts per second that is 2,000 × 48 KB ≈ 96 MB/s of page writes for 400 KB/s of actual new data. In practice it is better than that, because several inserts landing on the same hot page are coalesced before the next checkpoint — but that coalescing is exactly what you lose when the indexed column is random.

Which gives the single most actionable rule in this whole area: an index on a random value scatters your writes. An index on created_at appends to one leaf page at the right-hand edge of the tree, which stays in memory and gets written once per checkpoint. An index on a UUIDv4 primary key sends every insert to a different leaf page, so every insert dirties a fresh page, causes page splits, and blows out your buffer pool's working set. This is why UUIDv7 and ULID exist: same uniqueness, timestamp-prefixed, so inserts stay clustered at the end of the tree. If a candidate proposes a UUID primary key in a write-heavy design, "which UUID version?" is a fair and revealing question.

So indexes are not free lookups you sprinkle on. Each is a write-path cost you pay forever for a read-path win you should be able to name, and an index no plan uses is pure loss. Every mature production database has several.

The second hop most people forget

Finding the index entry is not the same as having the row. What happens next depends on the engine, and the difference shows up in interviews about MySQL versus Postgres.

In InnoDB the table is its primary key B-tree, and a secondary index's leaf stores the primary key. A lookup by email is therefore two descents: the email index to get the PK, then the PK index to get the row. In Postgres the table is an unordered heap and the index stores a tuple pointer, so it is one descent plus one heap read.

Either way there is a second random read per matching row — which is what turns "the index is being used" into "the query is still slow".

The fix is a covering index: put every column the query needs into the index itself, so the engine never touches the table. Postgres calls the resulting plan an index-only scan.

One Postgres caveat that trips people in production: an index-only scan must still confirm visibility, and can only skip the heap for pages marked all-visible in the visibility map. On a table updated constantly and vacuumed rarely, EXPLAIN ANALYZE shows a non-zero Heap Fetches and the covering index quietly degrades back to two hops.

Composite indexes: the column order is the design

A composite index on (a, b, c) is one B-tree sorted by a, then b within equal a, then c. Everything about what it can do follows from that, via the leftmost prefix rule: the engine can seek using a contiguous prefix of the columns, starting from the left, with at most one range predicate at the end of that prefix.

Take CREATE INDEX ON tickets (tenant_id, status, created_at):

Query predicate	Can it seek?
tenant_id = 42	Yes — one-column prefix
tenant_id = 42 AND status = 'open'	Yes — two-column prefix
tenant_id = 42 AND status = 'open' ORDER BY created_at	Yes, and the sort is free
tenant_id = 42 AND created_at > $1	Seeks on tenant_id only, then filters each entry
status = 'open'	No seek — the leftmost column is missing
tenant_id = 42 ORDER BY created_at	Seeks, but must sort — status sits in between

The last two rows are the interesting ones. status = 'open' alone cannot seek, because the entries for open tickets are scattered across every tenant's section of the tree. Postgres may still scan the whole index if it is much narrower than the table, and MySQL 8.0's index skip scan can rescue the case where the skipped column has few distinct values — but neither is something to design around.

The final row is the rule I would state as a position: put equality predicates first, then the column you range-scan or sort on. With (tenant_id, status, created_at), a query that filters on tenant and sorts by date without constraining status cannot use the ordering, because within a tenant the entries are ordered by status first. Reorder to (tenant_id, created_at, status) and that query sorts for free but loses the seek straight to open tickets. One index cannot do both; pick by which query matters.

Here is the version I would write for a ticket queue:

-- the query, run thousands of times a minute
SELECT id, subject, created_at
  FROM tickets
 WHERE tenant_id = 42
   AND status = 'open'
 ORDER BY created_at DESC
 LIMIT 20;

-- equality columns first, then the sort column, then the payload
CREATE INDEX idx_tickets_open_queue
    ON tickets (tenant_id, status, created_at DESC)
   INCLUDE (subject);

That index seeks to (42, 'open'), reads twenty consecutive leaf entries in the order asked for, and returns without touching the table. No sort, no heap fetches, and the cost is independent of how many tickets tenant 42 has — which matters, because the tenant that files a million tickets is the one that pages you.

Two portability notes: DESC in an index definition needs MySQL 8.0 or later, and INCLUDE is Postgres 11+ — in MySQL you append the payload column to the key instead.

When you read the plan, check structure rather than timing: no Sort node, and Heap Fetches: 0 on an index-only scan. A query that got faster because the data was already cached will get slow again at 3 a.m.

Why the planner ignores your index

"I added the index and it is not using it" is usually the planner being right.

Set up the arithmetic. A 10 million row table, 8 KB pages, about 40 rows per page: 250,000 pages. Postgres costs a sequential page at 1.0 and a random page at 4.0 by default.

• Sequential scan: 250,000 × 1.0 = 250,000 cost units.
• Index scan matching 0.1% of rows (10,000 rows, scattered): 10,000 × 4.0 = 40,000. The index wins comfortably.
• Index scan matching 1% of rows (100,000 rows, scattered): 100,000 × 4.0 = 400,000. The scan wins.

So with default costs the crossover sits somewhere between 0.1% and 1% selectivity, and above that an index makes the query slower — you are doing a worse-ordered version of a full scan with extra tree descents on top. This is not a planner bug; it is the reason random_page_cost exists.

That default is also worth arguing about: 4:1 describes a spinning disk. On NVMe the real ratio is nearer 1.5:1, so leaving random_page_cost at 4.0 systematically pushes the planner toward scans it should not be choosing. Setting it to 1.1 is a common and defensible production change.

The other three reasons a planner skips an index, in rough order of how often I have seen them:

• Stale statistics. Row estimates come from sampled histograms. Bulk-load 10 million rows and the estimate is off by orders of magnitude until ANALYZE runs.
• The predicate is not sargable. WHERE lower(email) = $1 cannot use an index on email; it needs one on lower(email). Same for created_at::date = $1 and a leading-wildcard LIKE '%foo'.
• Type mismatch. Comparing a varchar column to an integer literal coerces the column, not the literal, and the index is gone.

The other family: LSM trees

B-trees update in place, which makes their reads predictable and their writes expensive. Log-structured merge trees invert that bargain, and they sit under RocksDB, LevelDB, Cassandra, ScyllaDB and HBase — so the question comes up whenever a design involves very high write volume.

An LSM write goes to a write-ahead log and an in-memory sorted structure (the memtable) and returns. When the memtable fills, it is flushed to disk as an immutable, sorted file — an SSTable — in one large sequential write. Background compaction then merges SSTables into larger ones, discarding superseded versions and deleted keys.

Reads are where the LSM gives something back. A key may live in the memtable or any SSTable, so a lookup potentially checks many files. Two things bound it: each SSTable carries a Bloom filter, so a key absent from a file is rejected in memory with no I/O, and leveled compaction keeps each level's files non-overlapping, so at most one file per level can hold the key. In practice a point read is one real disk read plus some filter checks.

Range scans are the genuinely weaker case: the engine opens an iterator per level and merges them, where a B-tree walks one linked list of leaves.

	B-tree	LSM tree
Write path	in place, random page writes	memtable, then sequential flush
Write amplification	~41x for a 200 B row in an 8 KB page, plus WAL	~10x per level descended; 10–30x measured in RocksDB
Point read	3–4 page reads, predictable	Bloom-filtered; usually 1 real read
Range scan	one pass along linked leaves	merge iterators across levels
Space	fragmentation; leaves often ~70% full	~1.1x with leveled compaction, but tombstones linger
Latency shape	flat	spiky under compaction
Engines	InnoDB, Postgres, WiredTiger, SQLite	RocksDB, LevelDB, Cassandra, ScyllaDB, HBase

My default is the B-tree, and it should be the interview default too: it is what Postgres and MySQL give you, its latency is predictable, and most systems are not write-bound. I would reach for an LSM engine when ingest rate is the binding constraint and the pattern is point reads or short scans by key — time-series, event logs, counters, a write-heavy key-value store. Volunteering that an LSM trades read and space predictability for write throughput, rather than being simply "faster", is what reads as experience. It also feeds the choice in SQL vs NoSQL: the storage engine, not the query language, is usually what the write-ceiling argument is about.

What indexing does not solve

Naming the limits is what separates understanding the mechanism from having memorised it.

Write throughput. Indexes make writes more expensive, never cheaper. If your bottleneck is ingest, every index you add is working against you. The answer there is fewer indexes, a different storage engine, or batching — not better indexing.

Data volume past one machine. An index makes a 10 TB table queryable; it does not make it fit on a host, and it does nothing for the write IOPS ceiling of a single primary. That is what database sharding is for, and an index is what makes each shard fast after you have split it.

Hot rows and contention. An index on account_id does not help when ten thousand concurrent transactions all update the same row. The cost there is lock waits, not page reads, and no index layout changes that.

Large aggregations. A GROUP BY day over a year of data has to touch all of it. An index can supply a better order and avoid a sort; it cannot avoid the read. That wants a materialised view, a rollup table, or a column store.

Queries nobody anticipated. Indexes serve known access patterns, which is why "what are the access patterns?" comes before "what's the schema?".

The alternatives worth naming

Each of these is a better answer than an index in a specific case, and saying when is the signal.

A materialised view. A covering index removes the heap fetch; a view removes the computation. For an expensive aggregation read far more often than it changes, the view wins — at the cost of staleness and a refresh strategy.

A cache. If the hot query set is small and tolerates staleness, 100 µs from Redis beats 400 µs from a perfectly indexed B-tree and offloads the database entirely — see caching strategies. The failure mode to respect: a cache hides a missing index until it goes cold, and then you find both problems at once.

A dedicated search index. Full-text relevance ranking, fuzzy matching and faceting are not B-tree problems. Postgres GIN with tsvector goes surprisingly far; past that, Elasticsearch or OpenSearch with a real inverted index. Vector similarity search is the same argument again with HNSW instead.

A column store. For analytical scans over billions of rows, ClickHouse or a warehouse beats any row-store index: it reads only the columns in the query and compresses them heavily. ClickHouse's "primary key" is not even a B-tree — it is a sparse index with one mark per 8,192 rows, a useful reminder that "index" names a family, not a structure.

BRIN, for naturally ordered data. A block range index stores only the min and max per block range. On a 1 TB append-only table ordered by time it can be a few megabytes where a B-tree would be tens of gigabytes, and it answers time-range queries well enough. Useless when physical order and value are poorly correlated.

Partial and expression indexes. Often the right answer instead of a wider index. CREATE INDEX ... WHERE status = 'open' indexes only the 2% of rows that are open — small enough to stay in memory, and cheap enough that closed-ticket writes never touch it.

Using it in an interview

Indexing rarely gets its own question. It shows up as a follow-up once you have said "we store it in Postgres" and the interviewer wants to know whether you can make that real. The order that lands:

1. State the query first, not the index. "The hot read is the open-ticket queue per tenant, ordered by date, twenty at a time."
2. Derive the index from it. Equality columns first, then the sort column, then any payload you want to avoid a heap fetch for.
3. Say what it costs. One more B-tree per insert, and name roughly what that does to write amplification.
4. Volunteer the selectivity limit. Above a few percent of the table the planner should prefer a scan, and that is correct behaviour.
5. Pre-empt the follow-up by naming one thing the index does not fix — hot rows, ingest rate, or an aggregation.

Steps 3 and 4 are where most candidates go quiet, and they are what distinguishes someone who has tuned a production database from someone who has read about one. "Add an index" is the beginning of an answer; "this index, in this column order, costing this much on write, useful up to this selectivity" is the whole of it.

If you want to hear how that sounds under pressure — including the follow-up about what happens to your write throughput at ten times the volume — you can run a system design mock interview by voice on Whitepad.