In-place updates versus append-only writes
A B-tree organizes data in sorted blocks and modifies them in place. Inserting a new key finds the appropriate leaf block, inserts the key, and if the block overflows, splits it. Reads are fast because data is organized by value: a range query scans contiguous sorted blocks. Updates are also in-place and immediate.
An LSM (Log-Structured Merge) tree is append-only: writes go to an in-memory buffer (memtable), and when full, are flushed as an immutable sorted file (SSTable). Read amplification occurs because a key might exist in multiple SSTables. Compaction merges overlapping SSTables in the background, eventually consolidating old data. LSM trees sacrifice read performance for write throughput and reduced write amplification.
Tradeoffs and database system choices
B-trees win when reads are frequent and latency-sensitive. Random writes in B-trees cause seeks on disk, but batch-ordered queries are fast. LSM trees excel under write-heavy workloads with sequential I/O: writes to the memtable and sequential SSTables are much faster than random B-tree seeks. Compaction can be deferred, amortizing its cost.
RocksDB and LevelDB use LSM structures and dominate write-heavy applications. MySQL and PostgreSQL use B-trees for their maturity and simple read semantics. Modern systems (CockroachDB, Cassandra) use LSM variants. The choice depends on workload: OLTP favors B-trees, OLAP and streaming favor LSM. In practice, hybrid approaches tune write-amplification, read-amplification, and space-amplification tradeoffs.