Indexing (B-Tree vs LSM)

Without an index, finding a row means scanning the whole table — checking every record until you find the one you want. That’s O(n), and on a billion rows it’s a coffee break. An index is a second, specially-organized copy of some of your data that turns that scan into a fast lookup. It’s the single biggest lever you have over database read performance.

But there is no free lunch, and indexing states the central trade-off of this whole part with unusual clarity: an index buys faster reads and charges you in slower writes and extra storage. Every write must now update the table and every index on it. The art of indexing is spending that write tax only where the read speedup is worth it.

Why an index speeds reads (and slows writes)

Think of a book’s index. To find every mention of “Paxos,” you don’t read all 400 pages — you flip to the back, find “Paxos → p. 211, 230,” and jump. The index is a sorted structure that maps a key (the value you search by) to a location (where the full row lives).

Without index:   SELECT * WHERE email = 'x'  →  scan all N rows        (slow, O(N))
With index:      email index → row location  →  one lookup            (fast, O(log N))

The cost shows up on the other side. Every INSERT, UPDATE, or DELETE must keep that sorted structure correct, which means extra work and extra disk. Index a column you never search by and you’ve bought pure overhead. This is why “add an index” is the first tuning move and “you have too many indexes” is a real performance bug.

Family 1: the B-tree (read-optimized, update-in-place)

The B-tree (specifically the B+tree) has been the default index structure since the 1970s and powers Postgres, MySQL/InnoDB, SQL Server, and most relational databases. It keeps keys sorted in a shallow, wide tree of fixed-size pages (typically 4–16 KB), so any key is reachable in a handful of disk hops.

                       ┌───────────────────────┐
                       │      [  30  |  60 ]    │      root (1 page)
                       └────┬───────┬───────┬───┘
              ┌─────────────┘       │       └─────────────┐
        ┌─────▼─────┐         ┌─────▼─────┐         ┌─────▼─────┐
        │ [10 | 20] │         │ [40 | 50] │         │ [70 | 80] │   internal
        └──┬──┬───┬─┘         └──┬──┬───┬─┘         └──┬──┬───┬─┘
           ▼  ▼   ▼              ▼  ▼   ▼              ▼  ▼   ▼
        ┌──────────────────────────────────────────────────────┐
        │  leaf pages: sorted keys → row pointers, linked left→right │
        └──────────────────────────────────────────────────────┘

To find key 50, you start at the root (50 is between 30 and 60), descend to the right internal node, then to the leaf. Three page reads, billion rows or not — the tree is balanced and only a few levels deep. The leaves are linked in order, so range scans (“all keys between 40 and 70”) are cheap: find the start, walk sideways.

The defining trait: B-trees update in place. Changing a key overwrites the page where it lives. That makes reads predictable and ranges fast, but it means every write seeks to a specific spot on disk and rewrites a whole page — random I/O, which spinning disks hate and even SSDs prefer to avoid.

Family 2: the LSM-tree (write-optimized, append + compact)

The Log-Structured Merge-tree flips the priority to make writes cheap. It’s behind Cassandra, RocksDB, LevelDB, HBase, and the storage engines under many modern key-value stores.

The trick: never seek to update in place; only ever append.

   write  →  [ MemTable ]      in-memory, sorted (fast)
                  │ when full, flush to disk as an immutable file
                  ▼
            [ SSTable L0 ] [ SSTable L0 ] ...   sorted files, never modified
                  │  background COMPACTION merges + sorts them
                  ▼
            [ SSTable L1 (bigger, merged) ] → [ L2 ] → ...

Writes go to an in-memory sorted table (the memtable) plus an append-only log for durability — both sequential, both blazing fast. When the memtable fills, it’s flushed to disk as an immutable sorted file (an SSTable). Over time you accumulate many SSTables, so a background process called compaction merges and re-sorts them into fewer, larger files, discarding overwritten and deleted keys along the way.

The cost lands on reads. A key might live in the memtable, or any of several SSTables, so a read may have to check multiple files. LSM engines fight this with Bloom filters (a probabilistic “is this key definitely not here?” check that skips most files) and by keeping files sorted, but reads still do more work than a B-tree’s tidy descent.

The three amplifications

The honest way to compare these families is through three “amplification” costs:

	B-tree	LSM-tree
Read amplification (extra reads per lookup)	Low — one path down the tree	Higher — may check several SSTables
Write amplification (extra writes per write)	Page rewrites; moderate	Compaction rewrites data many times
Space amplification (extra disk per byte)	Some empty page space	Stale copies until compaction reclaims them

There’s no universal winner

B-trees win when reads (especially range reads) dominate and writes are modest — classic OLTP. LSM-trees win when you’re absorbing a firehose of writes — time-series, logging, event ingestion. Many systems now let you pick the engine (MySQL with MyRocks, for instance). The choice is just which amplification you can most afford for your workload.

Covering indexes: skipping the table entirely

A normal index gets you the location of the row, then a second read fetches the row. A covering index includes the actual columns you need, so the query is answered from the index alone — the table is never touched.

Query: SELECT name FROM users WHERE email = ?

Plain index on (email):    email → row location → read table → name   (2 hops)
Covering index (email, name): email → name (right there in the index) (1 hop)

This buys a real read speedup for hot queries — at the cost of a fatter index (more storage, more write tax, because the included columns must be kept in sync). Like every indexing decision, it’s the same bargain in miniature: pay on write to win on read.

By the numbers — a B-tree’s shocking shallowness

A B+tree’s whole magic is fan-out: each node is a page packed with keys and child pointers, so the tree stays shallow even at absurd scale.

   page size                        ≈ 8 KB
   per entry (key + child pointer)  ≈ 24 bytes
   fan-out = 8192 / 24              ≈ 340 children per node

   levels   rows reachable (≈ fan-out^levels)
     1                340
     2            115,000
     3         39,000,000
     4     13,000,000,000   ← billions of rows, only 4 levels deep

So any row in a billion-row table sits ~4 page reads away — and because the root and the next level are almost always cached in RAM, only the bottom level or two actually touch disk. That is why “add an index” turns an O(N) coffee-break scan into a sub-millisecond lookup, and why the tree’s depth barely grows as your table does. The flip side is the write tax: every insert may have to split a full page and ripple upward, which is the random I/O the LSM-tree trades away.

The thread

An index is a deliberate redundancy: a second copy of your data, organized for fast retrieval, kept in sync on every write. B-trees organize it for reading (sorted, update-in-place, great ranges); LSM-trees organize it for writing (append-only, compacted in the background). Covering indexes push the bargain further by answering queries without touching the table at all. In every case you are spending writes and storage to buy reads — so index the columns you search by, not the ones you merely store.

The architect’s lens

An index is the first tuning move and a real performance bug when overused — so weigh each one with the five questions:

• Why does it exist? Because without one, finding a row means scanning the whole table — O(N), a coffee break on a billion rows. An index is a second, sorted copy of some of your data that turns that scan into an O(log N) lookup.
• What problem does it solve? Read performance — the single biggest lever you have over query speed. A B-tree’s fan-out keeps any row ~4 page reads away even in a billion-row table, with the top levels cached in RAM.
• What are the trade-offs? You pay on write to win on read: every INSERT/UPDATE/DELETE must update the table and every index, plus extra disk. B-trees update in place (low read amplification, but random-I/O write tax); LSM-trees append and compact (cheap writes, but higher read and space amplification). The choice is just which amplification your workload can afford.
• When should I avoid it? On a column you never search by — that’s pure overhead, which is why “too many indexes” is a genuine performance bug. And avoid B-tree update-in-place under a write firehose (time-series, logging); reach for an LSM engine there instead.
• What breaks if I remove it? Every lookup degrades to a full O(N) table scan — sub-millisecond reads become seconds, and a read-heavy path that depended on the index collapses under load.

Check your understanding

1. Why does adding an index speed up reads but slow down writes? What exactly happens on each write?
2. Walk through how a B-tree finds a key, and explain why range scans are cheap on it.
3. What is the core trick of an LSM-tree, and what is compaction for?
4. Define read, write, and space amplification. For each index family, which one is the weak spot?
5. What is a covering index, and how does it restate the read-vs-write trade-off?

Show answers

1. An index is a second, sorted copy of some of your data that maps a key to a row location, turning an O(N) scan into an O(log N) lookup. Writes slow down because every INSERT, UPDATE, or DELETE must keep both the table and every index on it correct — extra work and extra disk on each write.
2. To find a key, you start at the root, compare against its separators to pick the right child, descend through internal nodes, and reach a leaf — a handful of page reads because the tree is balanced and shallow. Range scans are cheap because leaves hold keys in sorted order and are linked left-to-right, so you find the start and walk sideways.
3. The core trick of an LSM-tree is to never seek to update in place; only ever append — writes hit an in-memory sorted memtable plus an append-only log, then flush to immutable sorted SSTables. Compaction is the background process that merges and re-sorts accumulated SSTables into fewer, larger files, discarding overwritten and deleted keys.
4. Read amplification is extra reads per lookup, write amplification is extra writes per write, space amplification is extra disk per byte stored. The B-tree’s weak spot is write amplification (page rewrites / random I/O); the LSM-tree’s weak spots are read amplification (checking several SSTables) and space amplification (stale copies until compaction reclaims them).
5. A covering index includes the actual columns a query needs, so the query is answered from the index alone and the table is never touched. It restates the bargain in miniature: you pay on write (a fatter index, more storage and write tax) to win on read (one hop instead of two).