B-tree vs LSM tree

The decision

A B-tree keeps data in sorted pages on disk and changes a page in place. An LSM tree (log-structured merge tree) writes new data to a log and a memory table first. Later it writes sorted files that never change, and it merges them in the background. A B-tree is built for fast, steady reads. An LSM tree is built for heavy writes, and you pay with background work and reads that may check several files.

Choose a B-tree when

• Reads are much more common than writes, for example 10 reads or more for each write.
• You need predictable read time and cheap range reads. The leaves of the B-tree that databases use (a B+ tree) are linked in order.
• Transactions and updates in place matter, as in a relational database such as Postgres.
• Disk life matters and writes are modest. A B-tree with a warm cache writes each changed page once per flush, plus its log.
• You want no background merging that can fall behind.

Choose an LSM tree when

• Writes are heavy and steady, for example 20,000 rows per second of rider locations, events or messages.
• Data arrives in many small writes, and a read may look in several places.
• You can give the store spare disk speed and space for merging.
• Old data is dropped by time, so whole files can be thrown away together.
• The store is a wide-column or key-value database that is built this way, such as Cassandra or RocksDB.

The numbers that change the answer

All numbers are assumptions unless marked. Take 20,000 writes per second of 200 bytes each. The data rate is 20,000 x 200 = 4,000,000 bytes per second, which is 4 MB per second. A page is 8,192 bytes (the Postgres page size, as in the indexes lesson).

B-tree worst case. Every write lands on a different page, and nothing is shared. The disk writes 20,000 x 8,192 = 163,840,000 bytes per second, about 164 MB per second, in random places. That is 8,192 / 200 = 41 times the data. A big cache of hot pages lowers this a lot, so treat it as the worst case.

LSM write amplification. This is the bytes written to disk divided by the bytes the app wrote. RocksDB documents that leveled compaction is often larger than 10. Assumption: leveled gives 20 and size-tiered gives 6.

• Leveled: 4 MB x 20 = 80 MB per second, mostly in long runs.
• Size-tiered: 4 MB x 6 = 24 MB per second.

The ingest ceiling. Assumption: the disk can write 200 MB per second in long runs. Leveled: 200 / 20 = 10 MB per second, which is 10,000,000 / 200 = 50,000 writes per second. Size-tiered: 200 / 6 = 33 MB per second, about 167,000 writes per second. Above the ceiling, compaction falls behind. Files pile up, reads slow down, and the store slows or stops writes on purpose.

Disk life. Assumption: an SSD is rated for 600 TB of writes. Data sheets differ a lot, so check yours. Per day, the disk writes MB per second x 86,400 / 1,000,000 TB.

Write amplification is a hardware bill for both designs. An LSM tree pays it by design. A B-tree pays it when its cache is too small.

Point reads. Assumption: a B-tree page holds 300 entries. Then 40 million rows need 4 page reads, since 300 to the power of 3 is only 27 million. The top pages sit in memory. An LSM store with a Bloom filter of 10 bits per key has a false positive rate of 0.82 percent per file. With 6 levels, a key that does not exist costs about 6 x 0.0082 = 0.05 file reads. A key that exists costs about one file read plus the filter checks. Without filters, the missing key would check all 6 or more files.

Space. A size-tiered merge writes its new file before it removes the old ones. Merging 64 GB can need up to 64 GB of extra space for a while. Leveled needs less spare space and rewrites more.

What breaks with each choice

B-tree.

• Random writes hurt when the data is bigger than memory and keys arrive in random order. Each write reads and changes a page.
• Each write also goes to a log first, so the disk sees the data at least twice.
• Each index is another tree to change for every write.
• What you do: batch writes, use time-ordered keys, and add a follower for reads.

LSM tree.

• Compaction debt. If ingest passes the ceiling (50,000 writes per second leveled in the example), files pile up. Alarm on the number of files and on pending compaction bytes.
• Slow range and missing-key reads. A read merges several files. Bloom filters help for single keys, not for ranges.
• Tombstones. A delete adds a marker. The old rows go only when a merge covers them. A store with copies on other servers keeps tombstones for days (Cassandra's default is 10 days), so a big delete first increases disk use.
• Read spikes. Merges compete with reads for the disk. Cap the merge speed.

What it costs

All numbers here are assumptions.

• Money: the LSM store needs spare disk speed. Here, 80 MB per second of merging plus 4 MB per second of log is 84 of 200 MB per second, or 42 percent. It also needs extra space. A B-tree needs RAM for cache.
• People: tuning compaction is a skill. Plan for one engineer who knows it.
• Time to change your mind: the engine comes with the database. Moving from Postgres to Cassandra is a migration of months with dual writes. Some databases offer both engines, so test with real data first.

How each level answers

The question is: "Store 20,000 rider locations per second. Which engine?"

SDE-1: A B-tree changes sorted pages in place. An LSM tree appends to a log and merges sorted files later.

SDE-2: I pick an LSM store, because a write is one log append and one memory insert. I add Bloom filters so a read skips most files. I would pick a B-tree if reads dominated.

Senior: Leveled compaction turns 4 MB per second into about 80 MB per second of disk writes. That is 42 percent of a 200 MB per second disk with the log. The ceiling is 50,000 writes per second, so I watch pending compaction bytes. If compaction falls behind, I switch to size-tiered, add disks, or shard.

Staff: The engine matters through cost: disk life (87 days leveled and 290 size-tiered, in the example), disk count and compaction on-call work. I choose the engine the team can run, and I move a working Postgres only when a measured number forces it. Each quarter I measure write amplification, files per read and read time at the 99th percentile.

Say it in the interview

For 20,000 writes per second I would use an LSM store, because each write is a log append and a memory insert. The data is 4 MB per second, but leveled compaction makes it about 80, so I check disk room and alarm on compaction backlog. If reads dominate, a B-tree is the safer choice.

Common mistakes

• "LSM is always faster." It is faster for writes. A read may check several files, and merges use the disk.
• Ignoring write amplification. The app writes 4 MB per second and the disk writes 80. That limits throughput and shortens disk life.
• Forgetting that deletes add data. A tombstone is a new row. Disk use rises first and falls after a merge.
• Trusting a 5-minute benchmark. Compaction debt shows up after hours.

Sources

• RocksDB, leveled compaction (write amplification is often larger than 10; each level is 10 times larger by default): https://github.com/facebook/rocksdb/wiki/Leveled-Compaction (opens in a new tab) (checked 26 Oct 2026).
• RocksDB, Bloom filter (no false negatives; about 10 bits per key for about 1 percent): https://github.com/facebook/rocksdb/wiki/RocksDB-Bloom-Filter (opens in a new tab) (checked 26 Oct 2026).
• Cassandra, storage engine and compaction (the grace period for a tombstone is 10 days by default): https://cassandra.apache.org/doc/latest/cassandra/managing/operating/compaction/overview.html (opens in a new tab) (checked 26 Oct 2026).
• The write rates, the amplification factors of 20 and 6, the disk speed, the disk rating and the page counts are assumptions made for teaching. The other numbers are calculations shown above.