TL;DR - A lookup on an unindexed column reads the whole table; a B-tree turns it into 3 or 4 page reads. An index is a sorted copy of a few columns, so it speeds up matching reads and taxes every write. Know clustered versus secondary, the leftmost-prefix rule, covering indexes, and when the planner scans anyway.
30-second version (elevator pitch): "An index is a sorted structure mapping column values to row locations, so the database seeks in place of scanning. B-tree pages hold hundreds of entries, so 4 levels cover billions of rows, and range scans walk the leaf chain. Every index adds IO to each write, so I add them for queries I can name, put equality columns before range columns, and use a covering index for the hottest query."
Why a Lookup by Email Reads 20 GB
A users table holds 100 M rows at about 200 bytes each. Login runs SELECT id, password_hash FROM users WHERE email = ?. With email unindexed the engine checks every row: 100 M x 200 bytes = 20 GB per login. At 2 GB/s sequential that is 10 seconds per login, all of them sharing one disk.
With a B-tree on email, the lookup descends 4 levels, one 16 KB page per level: 4 x 16 KB = 64 KB. The top levels stay in memory, so the real cost is one or two SSD reads of about 100 microseconds.
How a B-Tree Index Works
What is an index? A separate structure holding one or more columns in sorted order, each entry pointing at its row.
What is a B-tree? A balanced tree whose nodes are fixed-size disk pages, 8 KB in Postgres and 16 KB in InnoDB. Internal pages hold separator keys and child pointers; leaf pages hold keys with row pointers. Every leaf sits at the same depth, so every lookup costs the same number of page reads; a full page splits in two and pushes a separator up.
What is fan-out? The number of children per internal page. At roughly 32 bytes per entry, a 16 KB page holds a few hundred, and fan-out compounds per level:
- -Height 3 at fan-out 300: 300^3 = 27 M entries.
- -Height 4: 300^4 = 8.1 billion entries.
So 100 M rows fit in height 4. The top two levels are 301 pages, under 5 MB, so they stay cached and a point lookup usually pays for one leaf read.
What is a B+tree? The variant every major database ships. All entries live in the leaves, and the leaves are linked left to right. A range query such as created_at BETWEEN a AND b descends once, then walks the leaf chain, which is also why ORDER BY on an indexed column can skip the sort.
Clustered, Secondary, Composite, Covering
Clustered Versus Secondary
What is a clustered index? One whose leaves hold the full rows, so the table is the index. InnoDB clusters every table on its primary key.
What is a secondary index? One whose leaves hold the indexed columns plus a row locator. In InnoDB the locator is the primary key, so a lookup by email is a double lookup: descend the email tree to get the id, then descend the primary key tree to get the row.
Keep the primary key small, because every secondary leaf entry carries a copy: an 8-byte bigint across 5 secondary indexes on 100 M rows is 4 GB of copies; a 36-byte UUID string is 18 GB. Keep it monotonic so inserts append to the rightmost leaf; random UUIDs split pages across the whole tree.
Composite Indexes and the Leftmost Prefix
What is a composite index? One B-tree over several columns, sorted by the first, then by the second within equal first values.
What is the leftmost-prefix rule? The tree seeks on a prefix of the column list from the left. An index on (tenant_id, created_at) serves filters on tenant_id, or on both. A filter on created_at alone finds its entries scattered across every tenant, so the planner scans.
Worked example: 100 M orders, 10,000 tenants, 10,000 orders each, hot query "tenant 7 in the last 24 hours", about 30 rows.
- -(tenant_id, created_at): seek to tenant 7, then to yesterday, read 30 adjacent entries.
- -(created_at, tenant_id): seek to yesterday, read every tenant's orders for that day, 10,000 x 30 = 300,000 entries, filter 299,970 away.
Rule: equality columns first, the range column next, then sort columns.
Covering Indexes
What is a covering index? One holding every column the query reads, so the engine answers from the leaves and skips the table. SELECT id FROM users WHERE email = ? is covered by any InnoDB index on email, since the leaf already carries the primary key.
What Indexes Cost on Writes
Each index is another B-tree to update. With 5 secondary indexes, one insert becomes 6 tree insertions, each dirtying a 16 KB page: around 96 KB of page writes for a 200-byte row, before the write-ahead log. That is write amplification, worst on random-valued columns, where each insert lands on a cold random leaf.
Rule of thumb: about 5 indexes on a write-heavy table, each named after the query it serves. Drop indexes whose usage counter stays at zero.
When the Planner Picks a Full Scan
- -Low selectivity. WHERE status = 'active' matching 90 percent of rows means 90 M random page fetches via the index; a sequential 20 GB scan is cheaper.
- -A function on the column. WHERE lower(email) = ? compares a computed value; the tree is sorted by the raw one. Add an expression index on lower(email).
- -A leading wildcard. LIKE '%gmail.com' matches anywhere, so sort order is useless; LIKE 'jim%' is a range seek.
Other types to name: hash (equality alone), bitmap (low-cardinality analytics) and inverted (full-text search).
LSM Trees Versus B-Trees
An LSM tree buffers writes in a sorted in-memory table backed by a sequential log, flushes it as an immutable sorted file, and merges files in the background (compaction). Writes are sequential, so ingest throughput is high; reads may consult several files (read amplification, tempered by bloom filters), and compaction spends background IO. B-trees update pages in place and give predictable point reads. Say LSM (Cassandra, RocksDB) for event ingest, B-tree (Postgres, InnoDB) for transactional tables.
Operating Indexes
- -Bloat. After heavy churn an index can sit at half density, doubling its cache footprint. Rebuild online and build new indexes concurrently so writes keep flowing.
- -Partial indexes. WHERE status = 'pending' on a jobs table indexes 1 percent of rows and stays tiny and hot.
- -Alternatives worth naming. Cache the hot lookup in Redis; denormalize a column onto the row that is read; hand free text to a search engine.
When to Use in Interviews
Raise indexing the moment you draw a table and name a query on it: "login by email, covering"; "orders by tenant and time, composite (tenant_id, created_at)"; "jobs queue, partial index on pending". For an ingest-heavy path, state the index budget and name LSM storage.
Summary
- -Scan versus seek - 20 GB per unindexed lookup versus 4 page reads.
- -Fan-out - 300^4 = 8.1 billion, so height 3 to 4 covers any OLTP table.
- -Secondary lookups - InnoDB leaves hold the primary key; keep it small and monotonic.
- -Leftmost prefix - Equality first, range next, then sort columns.
- -Write cost - Budget about 5 indexes on hot tables.
Interview Q&A
- -Why a B-tree over a hash index? - It serves equality, ranges and ordering in one structure.
- -How many rows fit under 4 levels? - About 8.1 billion at fan-out 300.
- -Index on (a, b): which queries use it? - Filters on a, or on a and b.
- -When does the planner ignore an index? - Low selectivity, a function on the column, or a leading wildcard.
- -LSM or B-tree for event ingest? - LSM, for sequential writes.
Disclosure: I build Pretense, a local proxy that swaps secrets, PII and code identifiers for stand-in tokens before a prompt leaves your laptop. Paste an EXPLAIN plan with its connection string into an AI assistant: table and column names come back byte-exact, and the credential stays a stand-in.
From the System Design Laws newsletter.
