Database Indexing: B-Trees and LSM Trees

1The core idea#

Start with what an index buys you, because the whole discussion hangs off this.

• An index is a second copy of your data, organized so you can find rows without scanning everything.
• Without one, finding a user by email in a 50 million row table means reading all 50 million rows: a full table scan touching maybe 400,000 pages at 16KB each, taking seconds.
• With one, you read maybe 4 or 5 pages off disk and answer in single-digit milliseconds.
• That is the whole pitch.

The interesting part is the data structure underneath. Almost every production database picks one of two families.

• B-Trees (really B+Trees): the default for relational databases. Postgres, MySQL/InnoDB, SQL Server, Oracle. An update-in-place structure: to change a row you find the exact page it lives on and overwrite it.
• LSM Trees (Log-Structured Merge Trees): the engine behind write-heavy stores. Cassandra, RocksDB, LevelDB, ScyllaDB, and the default backend in many time-series and key-value systems. An append-only structure: you never overwrite in place, you write new data and clean up later.

The mental model I use:

• A B-Tree is a sorted filing cabinet. Every record has a home, and to change it you walk to that drawer and swap the sheet.
• An LSM Tree is an accountant's ledger. You never erase a line, you append a new line that corrects the old one, and periodically you rewrite the book to throw out the stale entries.

2How it works#

Two structures, two very different write paths. Walk each one top to bottom.

B+Tree#

A B+Tree is a balanced tree where each node is one disk page, usually 4KB to 16KB.

• Internal nodes hold only keys and pointers to child nodes.
• The actual row data (or pointers to it) lives only in the leaf nodes.
• Leaves are linked left to right, so you can range-scan without climbing back up.

The tree stays shallow on purpose.

• Fan-out is several hundred keys per node, so a tree holding billions of rows is only 3 or 4 levels deep.
• A point lookup is 3 or 4 page reads, and the top levels sit in memory anyway, so in practice it is often 1 real disk read.

Writes are where it gets expensive.

• To insert a key you walk down to the correct leaf and modify that page in place.
• If the leaf is full, you split it into two and push a key up to the parent, which can cascade all the way to the root.
• Every write is a random write to a specific location on disk.
• On a spinning disk that is brutal: a 10ms seek per write caps you near 100 writes per second per disk.
• Even on SSD it means read-modify-write at the page level, plus write amplification from partially-filled pages.

LSM Tree#

An LSM Tree flips the write path.

• New writes go into an in-memory sorted structure called the memtable (often a skip list or balanced tree).
• They also go into an append-only write-ahead log on disk for durability.
• Both are fast: the log is a sequential append, the memtable is pure RAM.

When the memtable fills up:

• It gets flushed to disk as an immutable sorted file called an SSTable. These files are never modified.
• Over time you accumulate many of them, so a background process called compaction merges smaller SSTables into larger ones, dropping overwritten and deleted keys as it goes.

Deletes are the sneaky part.

• You cannot erase from an immutable file, so a delete writes a marker called a tombstone.
• The key looks deleted on read, and compaction physically removes it later.

Here is the LSM write and read path side by side.

Reads are the cost center for LSM.

• A key might be in the memtable, or in any of several SSTables.
• A read checks multiple places, newest first, until it finds the key.
• To avoid touching every file, each SSTable has a Bloom filter in memory that answers "this key is definitely not here" cheaply, so you only read files that might contain the key.
• A Bloom filter tuned to a 1% false-positive rate costs about 10 bits per key, so an SSTable holding 10 million keys needs roughly 12MB of RAM. Cheap insurance against a disk read.

3Trade-offs#

The honest one-liner, worth memorizing word for word:

B-Trees optimize reads and pay on writes. LSM Trees optimize writes and pay on reads and on background work.

Be precise with the terms, because interviewers care about them.

• Write amplification: bytes actually written to disk per byte of logical data. LSM compaction rewrites the same data several times as it moves down levels. B-Trees rewrite full pages even for a tiny change.
• Read amplification: pages read per logical lookup. LSM can touch several SSTables plus Bloom filters. A B-Tree lookup is a predictable handful of pages.
• Space amplification: disk used per byte of live data. B-Trees leave pages partially full (fragmentation). LSM temporarily keeps old versions and tombstones until compaction cleans up.

Two subtle points worth saying out loud in an interview.

• Compaction competes with live traffic for disk and CPU. If writes arrive faster than compaction can keep up, SSTables pile up at level 0, reads slow down because each read checks more files, and you get a stall. The write-optimized store can fall over under exactly the write load it was supposed to handle well, if it is under-provisioned.
• B-Tree writes are sequential in the WAL, but the actual data pages get written randomly on checkpoint. So "B-Trees do random writes" is true for the data files, not the log. Being precise here signals you have actually operated these systems.

4Where it is used#

Match the engine to the workload. This is the judgment the question is really testing.

Reach for a B-Tree engine when:

• Your workload is read-heavy or balanced, with lots of point lookups and range queries. An orders table, a user directory, anything behind OLTP.
• You need strong, predictable read latency. A dashboard query that must return in 20ms every time is happier on a B-Tree.
• You rely on relational features: joins, foreign keys, multi-column indexes, transactions. Postgres and InnoDB give you all of that on a B-Tree.

Reach for an LSM engine when:

• Writes dominate. Event ingestion, metrics, logs, IoT sensor data, a feed of clicks. Cassandra and RocksDB-backed stores were built for this.
• You are writing far more than you read back, or you read mostly recent data.
• You want cheap sequential writes and good compression on commodity disks at scale.

A worked example with real numbers#

Say you are building a time-series metrics pipeline taking 200,000 writes per second, each write a small 100-byte sample. That is 20MB of logical data per second, 1.7TB per day.

On a B-Tree:

• Each write lands on a random leaf page.
• Even if two samples share a 16KB page, you rewrite the whole 16KB page to change 100 bytes.
• With a working set larger than RAM, each write turns into a page read plus a page write.
• The random I/O pattern caps a decent NVMe SSD around 50,000 to 80,000 random page ops per second.
• You cannot sustain 200k writes per second on one node: you either shard across 4 or 5 nodes just to survive ingest, or you fall behind and your write queue backs up.

On an LSM store:

• Those same 200k writes per second are appends into the memtable plus one sequential WAL append.
• A single sequential WAL stream handles 20MB per second trivially, well under what one SSD does sequentially (500MB per second-plus).
• The memtable flushes to an SSTable every, say, 256MB, so roughly every 13 seconds you write one clean sequential file.
• Compaction then rewrites that data a few more times as it moves down levels. If levels have a 10x size ratio and data passes through 4 levels, you write each byte about 4 to 5 times.
• Write amplification is near 5x: you physically write around 100MB per second to absorb 20MB per second of logical data. Still comfortable sequential I/O, and it is why the LSM store absorbs the load on one or two nodes instead of five.

Now flip the workload.

• A product catalog is read 10,000 times for every write: 1 million reads per second, 100 writes per second.
• On a B-Tree each read is a clean 3-page hop, top two levels cached, so about 1 real disk read at sub-millisecond latency, predictable p99.
• On an LSM store that same read might check the memtable, miss, probe 4 SSTable Bloom filters, and read 1 or 2 of them off disk: 2x to 3x the read amplification for zero benefit, since writes were never the bottleneck.
• The catalog belongs on a B-Tree.

The specific numbers move with hardware and tuning, but the shape is the point: the write-heavy ingest workload is a disaster on a B-Tree and easy on LSM, and the read-heavy catalog is the reverse.

The families converge at the edges.

• InnoDB has a change buffer that batches secondary-index writes to soften the random-write cost.
• RocksDB can be tuned toward read-optimized compaction.
• They blur the line, but the defaults tell you what each was built for.

5Common pitfalls and gotchas#

These are the ones that bite in production, which is exactly why interviewers listen for them.

• Treating "add an index" as free. Every secondary index is another B-Tree (or another set of SSTables) that must be updated on every write. I have seen a table with 11 indexes where inserts were 5x slower than they needed to be. Indexes cost write throughput and disk, not just the obvious storage.
• Ignoring tombstones in LSM systems. Delete a lot of rows or write a lot of short-lived data in Cassandra, and tombstones accumulate. Reads that scan a range walk past thousands of dead markers, and queries slow to a crawl until compaction catches up. The classic outage: "we used a Cassandra table as a queue," which creates and deletes constantly and leaves a graveyard of tombstones in every partition.
• Forgetting compaction is a tax you pay later. LSM write latency looks amazing in a 60-second benchmark. Run it for an hour under sustained load and watch compaction kick in. Good answers acknowledge that LSM trades steady latency for occasional spikes.
• Write amplification on SSDs. Both structures write more than the logical data, which wears SSDs and eats IOPS. LSM compaction can rewrite data 10x or more as it cascades down levels. If someone asks "why is our SSD wearing out," this is a real answer.
• Assuming range scans are equal. B+Tree leaves are linked, so a range scan is a sequential walk. LSM has to merge sorted runs across SSTables, which is more work and more unpredictable. For heavy range-query workloads, the B-Tree usually wins.

6How it shows up in interviews#

Interviewers rarely ask "explain a B-Tree" directly.

• It surfaces inside a bigger design: "Design a metrics system," "Design a chat app's message store," "Why did your database choke?"
• The index discussion is how you justify your database choice.

What they probe:

• Can you connect workload shape to storage engine? Write-heavy pushes you toward LSM, read-heavy toward B-Tree. Saying that unprompted is a strong signal.
• Do you understand the three amplifications? Dropping "write amplification from compaction" at the right moment lands well.
• Do you know the failure modes? Tombstone buildup, compaction stalls, random-write cost. These separate people who read a blog post from people who ran the thing.

Here is the same question answered two ways.

Put the two next to each other and the difference is obvious. The weak answer names a tool. The strong answer picks a side, ties it to a number, names the cost it is accepting, says what it would monitor, and shows it would choose the other engine for a different workload. That last move, choosing differently given different load, is exactly the judgment the question is testing.

One more move that impresses: say what you would measure.

• p99 read latency.
• Compaction backlog.
• SSD write amplification.
• It shows you think past the whiteboard to running the system in production.

And get comfortable drawing the LSM write path from memory: WAL append, memtable insert, flush to SSTable, compaction. If you can draw it and explain why each step exists, you understand the structure better than most candidates who have only read about it.

Next, try the System Design Question walkthrough on designing a time-series metrics store, where this B-Tree versus LSM decision is the first fork in the road.