30-Second Glance
- B-Trees (in practice B+Trees) are the default OLTP index: sorted, paged,
O(log n)reads/writes, and native range scans. - InnoDB stores the table itself as a clustered B+Tree keyed by primary key; secondary indexes point back to PK values, not row addresses.
- A 16 KB page with ~500-way fan-out holds ~100M rows in 3–4 levels — almost every lookup is ≤ 4 page reads, mostly cache hits.
- The price is random-write I/O and page splits: great all-rounder, not the max-write-throughput option (see LSM).
Structure and Why Pages
A B-Tree keeps keys sorted in fixed-size pages (nodes), typically 4–16 KB to match disk blocks and SSD pages. Internal pages hold key → child-page-pointer separators; leaf pages hold the actual entries. In the B+Tree variant every major engine uses (InnoDB, PostgreSQL), internal nodes carry only separators and all values live in leaves linked as a doubly-linked list — which is what makes ORDER BY and range scans a cheap leaf walk instead of repeated tree descents.
The page size is a deliberate compromise: large enough to amortize a disk seek over hundreds of keys, small enough that a random 8 KB read costs ~100 µs on SSD and fits CPU caches. InnoDB defaults to 16 KB pages; PostgreSQL to 8 KB.
Concrete Numbers (InnoDB)
| Quantity | Typical value | Why it matters |
|---|---|---|
| Page size | 16 KB (InnoDB), 8 KB (Postgres) | Unit of I/O, locking, and caching |
| Fan-out (branching factor) | 200–1000 keys per page | 16 KB page / (~16-byte key + ~6-byte pointer) ≈ 500–1000 |
| Tree depth | 3–4 levels for 10M–1B rows | 500³ = 125M; so a 100M-row table is 3 hops + leaf |
| Point lookup | 3–4 page reads worst case, usually 0–1 (buffer pool hits) | Buffer pool (e.g. 75% of RAM) absorbs the top levels |
| Range scan (1000 rows) | ~1 descent + sequential leaf walk | 10–100× cheaper than 1000 point lookups |
| Write cost | Read-modify-write of leaf + possible page split cascading upward | Splits are the main write-amplification and fragmentation source |
Work the fan-out math in the interview: with 500-way fan-out, a 4-level tree addresses 500⁴ ≈ 6×10¹⁰ keys. Real tables rarely exceed 3–4 levels, which is why "B-Tree lookups are effectively constant-time" is a defensible one-liner — log₅₀₀(n) barely moves.
Clustered vs Secondary Indexes
InnoDB clusters on the primary key: the leaf pages are the rows, ordered by PK. A PK lookup walks straight to the row. A secondary index leaf holds (indexed-key, PK-value), so a secondary lookup costs two traversals: index → PK → row. Consequences interviewers probe:
- Choose narrow, monotonic PKs (auto-increment int/bigint). Random UUID PKs scatter inserts across leaves, causing page splits, fragmentation, and ~2–3× write slowdown on spinning disk.
- Covering indexes skip the second hop: if the query's columns are all in the secondary index, InnoDB answers from the index alone (
Using indexin EXPLAIN). - PostgreSQL differs: it uses heap tables + secondary indexes holding physical TIDs, with an indirection layer instead of clustering. That is part of the MySQL vs PostgreSQL trade-off.
Writes, Splits, and Crash Safety
Insert into a full leaf → the page splits into two half-full pages and the parent gains a separator, potentially cascading to the root (the only operation that grows tree depth). Splits cause write amplification (one logical row → several page writes) and leave pages ~69%-full on average (classic B-Tree fill-factor result), i.e. ~30% space overhead.
Crash safety comes from a write-ahead log (InnoDB redo log, Postgres WAL): every page mutation is first appended to the WAL, so a crash replays committed changes and discards torn pages. The WAL also enables the buffer pool to defer flushing dirty pages for seconds-to-minutes, batching random writes into fewer fsyncs.
Concurrency uses latch coupling (short page latches during descent) plus row-level locking and MVCC at the transaction layer — see Two-Phase Locking and Snapshot Isolation.
Trade-offs
| Approach | Pros | Cons | Use when |
|---|---|---|---|
| B+Tree (clustered) | Sorted + range scans; bounded RAM; mature tooling; good read/write balance | Page splits; random-write I/O; PK design sensitive (UUID penalty) | Default OLTP: orders, users, inventory — any workload with range predicates |
| Hash index | Faster point lookups, pure sequential writes | No ranges; keyspace in RAM | Point-only KV — see Hash Indexes |
| LSM-tree | Higher write throughput; cheap compaction-friendly writes | Read amplification; no in-place update; tuning-heavy | Write-heavy sorted logs — see LSM Trees and SSTables |
| Full-text / GiST / R-tree | Purpose-built for text, geo, vectors | Extra index size + write cost per index | Add alongside B-Tree, not instead of it |
Rule of thumb for index count: each secondary index taxes every write (one more tree to update). OLTP tables with >5 secondary indexes usually signal a modeling problem.
Interview One-Liners
- Q: Why is a B-Tree lookup effectively O(1) in practice? A: Fan-out of ~500 means even a billion-row table is 3–4 levels deep, and the top levels sit in the buffer pool — so most lookups cost ~1 physical read.
- Q: Clustered vs secondary index in InnoDB?
A: Clustered leaves hold full rows ordered by PK; secondary leaves hold
(key, PK)and need a second PK lookup unless the index covers the query. - Q: Why are random-UUID primary keys slow in InnoDB? A: They scatter inserts across random leaves, maximizing page splits, fragmentation, and buffer-pool churn vs monotonic keys that append to the rightmost leaf.
- Q: What is a covering index?
A: A secondary index containing every column the query needs, so the engine never touches the clustered row (
Using index). - Q: How do B-Trees survive crashes mid-split? A: WAL-first: page mutations are redo-logged before being applied, so recovery replays committed splits and discards torn pages.
- Q: When would you pick LSM over B-Tree? A: Sustained write throughput dominates and point/range reads tolerate merge cost — metrics, event logs, Cassandra-style workloads.