B-tree vs LSM-tree: inside your database's index

Choosing a database without knowing which structure it uses underneath is choosing in the dark. The two dominant families (B-tree and LSM-tree) solve the same problem with opposite philosophies, and each charges you in a different place.

First: why disk changes everything#

In memory, reading any address costs roughly the same. On disk, it does not.

Disk does not read bytes: it reads blocks, typically four or eight kilobytes. Reading one byte or reading four kilobytes costs practically the same.

And each access to a different location is expensive: on SSD, tens to hundreds of microseconds; on spinning disk, milliseconds, because the arm has to move.

That inverts the design criterion. In memory, you minimise comparisons. On disk, you minimise accesses.

A binary tree with a million items has twenty levels. If each level is a disk access, that is twenty accesses, which is unacceptable.

The solution is to make each node large, the size of a block, with hundreds of children instead of two. The tree becomes short.

B-tree: predictable reads#

Each node occupies a disk page and holds hundreds of keys with their pointers. With a branching factor of around three hundred, a three level tree addresses twenty seven million records.

Three accesses in the worst case, and the first two levels are almost always in memory, so in practice it is one.

The variant every relational database uses is the B+tree: the data lives only in the leaves, and the leaves are linked to each other in a list. That keeps the internal nodes lean (more keys fit per page) and turns a range scan into walking a linked list, with no going up and down.

Writes: the page is read, changed and written back. If it filled up, it splits in two and the parent is updated. Random writes: every update touches a different page on disk.

Result: predictable, fast reads, including ranges and ordering. Middling writes at high volume.

Who uses it: Postgres, MySQL/InnoDB, Oracle, SQL Server, SQLite. Practically the entire relational world.

LSM-tree: sequential writes#

The LSM-tree starts from a different premise: random writes are expensive, so never do a random write.

Every write goes into an ordered in-memory structure (the memtable) and into a sequential log on disk, the WAL, which exists to recover after a crash.

When the memtable fills up, it is flushed to disk all at once, as an ordered, immutable file: an SSTable. Writes are always sequential, always fast.

The price shows up on reads. A record may be in the memtable or in any of the files, newest to oldest. To avoid opening all of them, each file has a Bloom filter, which answers instantly "definitely not here", and saves the read.

And since files accumulate, there is compaction: a background process that merges files, discards old versions and removes what was deleted.

Who uses it: Cassandra, RocksDB, LevelDB, HBase, ScyllaDB, and the storage engine of several things you use without knowing, including many time series databases.

Amplification: the three bills#

This is the vocabulary that lets you compare the two honestly.

Write amplification: how much the disk actually writes for every byte you stored.

In LSM, the same data is rewritten at each compaction level. One megabyte you wrote can turn into ten megabytes of real writes. That wears out SSDs and eats I/O bandwidth.

In B-tree, you rewrite a whole page to change one row. That amplifies too, but more predictably.

Read amplification: how many accesses are needed to find a record.

In B-tree, it is the number of levels: small and constant.

In LSM, it is the number of files that must be consulted: variable, and that is why the Bloom filter matters so much.

Space amplification: how much space is used beyond the useful data.

In LSM, old versions not yet compacted take up space.

In B-tree, pages deliberately leave free space so future inserts fit: fragmentation by design.

The decision table#

Pick B-tree when

• ·range reads and ordering are frequent
• ·predictable latency matters more than peak throughput
• ·you need rich ACID transactions
• ·the pattern is more reads than writes

Pick LSM when

• ·write volume is high and continuous
• ·access is by key, not by range
• ·compression matters: immutable sorted files compress better
• ·you tolerate latency variance

The detail that decides it in practice#

LSM's latency variance during compaction is real, and it is what surprises people who migrate.

The p50 can be excellent while the p99 jumps whenever a large compaction is running. If your product has an aggressive tail SLO, that has to go into the calculation, and there are different compaction strategies (levelled, size tiered) that trade amplification for predictability.

On the other side, B-tree suffers from concurrent writes to the same page and from fragmentation over time, which shows up as slow degradation that only a VACUUM or REINDEX fixes.

Neither is free. The right question is never "which is better", it is "which bill would I rather pay".

What this changes in your day#

Three concrete things:

1. When choosing a database, look up which structure it uses. That tells you more about behaviour under load than the marketing page does.

2. When investigating irregular latency on an LSM database, look at compaction metrics before anything else.

3. When investigating slow degradation on a B-tree database, look at fragmentation, bloat and stale statistics.

Knowing the name of the structure turns "the database is behaving strangely" into a testable hypothesis.