LSM Tree
also: log-structured merge tree
Write fast by appending; read by merging sorted layers — the engine inside Cassandra, RocksDB, LevelDB.
An LSM tree buffers writes in a sorted in-memory table, flushes it as an immutable sorted file (SSTable), and background-compacts files into larger sorted runs. Writes become sequential appends (fast); reads may consult several layers, helped by bloom filters that skip files cheaply. The opposite trade of a B-tree: LSM favors write throughput, B-trees favor read latency.