How Indexes Work — B+tree Internals

Why a lookup needs an index at all

WHERE id = 42 on an unindexed table is a full table scan — read every row, O(n). An index is a separate sorted structure that turns that into O(log n). Almost every relational database uses a B+tree for it — here's why and how.

Why a B+tree, not a binary tree or a hash

Disks (and SSDs) read in pages (~8 KB), and the cost is the number of page reads. A binary tree wastes that — one key per node, ~30 levels for a billion rows = ~30 reads. A B+tree packs hundreds of keys into one page (high fanout), so the tree is only ~3–4 levels deep for a billion rows → ~3–4 page reads per lookup. A hash index does equality in O(1) but can't do ranges or ORDER BY — which is why B+tree is the default.

Structure & the two operations

• Internal nodes hold only routing keys + child pointers (which subtree to descend).
• Leaf nodes hold the actual keys + row pointers, and are chained as a sorted doubly-linked list.

Point lookup (=): start at the root, follow the pointer for your key's range down to the leaf — ~3–4 reads. Range scan / ORDER BY / BETWEEN: descend to the start leaf, then walk the leaf links sideways — this sideways chain is exactly why B+tree beats hash for ranges and sorted output.

Trace: looking up key 60

1. Root. Routing keys are [40, 80]. 60 falls in the 40 ≤ key < 80 range, so follow the middle child pointer.
2. Internal/leaf. The child node contains [40, 50, 60, 70]. 60 is present, so the leaf entry gives the row pointer (or the row itself if the index is clustered).
3. Range continuation. A query for WHERE key BETWEEN 60 AND 100 would stop at the 60 entry, then use the leaf's right-link to scan 70, 80, 90, 100 sequentially without climbing back to the root.

Inserts & Deletes: The Mechanics of Splits and Merges

B+trees remain perfectly balanced because they grow from the bottom up during insertions and shrink during deletions. When a node exceeds its maximum capacity, it splits; when a node falls below minimum capacity, it merges or redistributes keys.

Clustered vs secondary (the hop that surprises people)

• Clustered index (InnoDB primary key): the table rows are the leaf nodes — data stored in key order. One lookup, you're done.
• Secondary index: its leaf stores the PK (or row-id), not the row. So WHERE email=? finds the PK in the email index, then does a second lookup in the clustered index to fetch the row — a "bookmark lookup." A covering index avoids it (next page).

When-NOT to reach for a B+tree (and when an extra index hurts)

B+tree is the default for a reason, but it is not free and not always the right structure:

• Write-heavy, append-mostly ingest (logs, metrics, CDC). Every secondary B+tree index turns one row insert into multiple random leaf updates and occasional splits — write amplification. LSM-tree engines (RocksDB, Cassandra, InnoDB change-buffer helps only so much) batch writes into sequential SSTables and absorb this better. If your primary pain is ingest rate, not point-lookup latency, prefer LSM (or fewer indexes), not "one B+tree per column."
• Random primary keys (UUIDv4 as clustered PK). Inserts hit random leaves → constant page splits, fragmentation, poor cache locality. Prefer sequential/time-ordered keys (bigserial, ULIDs, UUIDv7) for the clustered index; keep a secondary unique index on the external UUID if clients need it.
• Pure equality at extreme scale with no ranges. Hash indexes (Postgres non-unique hash, some engines' hash) can win for = only workloads. You give up BETWEEN, ORDER BY, prefix scans, and often durability/replication maturity — rare as a default choice.
• Over-indexing. Each index is maintained on every INSERT/UPDATE/DELETE of indexed columns. An index that is never used in WHERE/JOIN/ORDER BY is pure write tax + storage. Audit with unused-index stats; drop or replace with a partial/covering index that matches real predicates.
• Partial indexes (Postgres) when only a slice is queried: CREATE INDEX … ON orders(created_at) WHERE status = 'open' — smaller tree, less write cost for closed rows that never hit the index. Prefer partial over full when the predicate is stable and selective.
• Covering / INCLUDE indexes when the query only needs indexed columns: avoid the bookmark hop to the heap. Do not INCLUDE wide columns you rarely select — you inflate every leaf for a rare query shape.

Interview drills

1. L1: Why ~3–4 disk reads for a billion-row B+tree lookup?
   Answer: High fanout (hundreds of keys per ~8KB page) ⇒ tree height log_fanout(n) ≈ 3–4.
2. L2: Why can B+tree do BETWEEN efficiently and a hash index cannot?
   Answer: Leaves are a sorted linked list; descend to start key then walk sideways. Hash scatters equal ranges across buckets.
3. L3: You added five secondary indexes "for performance" and writes halved. What happened?
   Answer: Each write updates every secondary leaf (and may split). Write amplification; drop unused indexes or use partial/covering carefully.
4. L4: Clustered PK is UUIDv4; insert p99 latency climbs with table size. Why, and what would you change?
   Answer: Random inserts scatter across leaves → splits + cache misses. Switch to sequential/time-ordered clustering key; secondary unique on UUID if needed.
5. L5: When would you argue for an LSM store over B+tree for the primary access path?
   Answer: Sustained high ingest, range scans over time-ordered keys acceptable via SSTables, point reads secondary; accept compaction cost and read amplification trade-off.

Takeaways

• Index = sorted B+tree → O(log n); high fanout means ~3–4 page reads even for billions of rows.
• Leaves are a linked list → B+tree (not hash) for ranges/ORDER BY; hash only for equality.
• Every index adds write cost (updates + splits) — index deliberately; prefer partial/covering over reflexive full indexes.
• Secondary-index lookups may need a second hop to the clustered index.
• When-NOT: random clustered PKs, write-heavy ingest (consider LSM / fewer indexes), unused indexes, pure-equality-only niches for hash.

Re-authored for this guide; B+tree diagram hand-authored as SVG. Follows CMU 15-445 (Andy Pavlo) and DDIA ch. 3. See also: Indexes in Practice, How a Query Executes, Storage Engines — B-tree vs LSM-tree.