B-Tree vs LSM-Tree

Two engine families, one read-versus-write trade

Every durable database is built on one of two storage engine families, and the choice is fundamentally a read-versus-write tradeoff. Knowing which one sits under Postgres versus Cassandra is the difference between guessing at a database and reasoning about one.

B+tree: in-place pages, fast reads and ranges

A B+tree (Postgres, MySQL/InnoDB, most SQL engines) keeps data in fixed-size pages, typically 8KB or 16KB, arranged as a balanced tree with all rows in the leaf pages. Updates happen in place: to change a row you find its leaf page, load it into memory, modify it, and eventually write the whole page back. This gives excellent point reads (a lookup is 3 to 4 page reads for billions of rows) and, crucially, excellent range scans, because leaves are linked in sorted order, so "created_at between X and Y" is a sequential walk. The cost is write amplification: changing one 200-byte row can force an 8KB page write, plus a write-ahead log record, and page splits when a page fills. Random in-place writes are also unfriendly to SSDs, which prefer large sequential erases.

LSM-tree: append-only writes, compacted reads

An LSM-tree (Cassandra, RocksDB, ScyllaDB, LevelDB) inverts this. Writes go to an in-memory sorted structure, the memtable, plus a sequential commit log. When the memtable fills it is flushed to disk as an immutable, sorted SSTable. Writes are therefore append-only and sequential, so throughput is very high and SSD-friendly. The catch is reads: a key might live in the memtable or in any of several SSTables, so a read may have to check many files. Two mechanisms rescue read latency. Bloom filters (a small probabilistic set per SSTable) let a read skip an SSTable that definitely does not contain the key. Compaction merges SSTables in the background, discarding overwritten and deleted (tombstoned) rows, which bounds how many files a read must touch.

The three amplifications

• Write amplification: bytes written to disk per byte of logical write. B-tree pays it via full-page writes and the WAL. LSM pays it via compaction rewriting the same data across levels.
• Read amplification: disk reads per logical read. LSM is worse (multiple SSTables plus bloom checks); B-tree is a clean 3 to 4 pages.
• Space amplification: disk used per byte of live data. LSM can hold stale copies until compaction reclaims them; B-tree wastes space via partially-full pages and fragmentation.

Interview nuance: compaction is the LSM landmine. It runs in the background and competes for disk I/O and CPU, so under sustained write pressure you get compaction stalls and latency spikes right when you are busiest. "Leveled" compaction (RocksDB default) gives better read and space amplification but more write amplification; "size-tiered" (Cassandra default) is the reverse. Naming this tradeoff signals you have actually operated one.

The LSM write path

Step 1 / 4

Stage 1 of 4: A write never edits a page in place; the whole path is append-only and sequential, which is why LSM write throughput is high and SSD-friendly.

Recap: B-tree updates pages in place for fast reads and range scans at the cost of write amplification; LSM appends to a memtable then compacts immutable SSTables for high write throughput, using bloom filters and compaction to keep reads sane.