B-Trees, LSM Trees, and Write-Ahead Logs

B-tree-family indexes keep keys ordered and support point lookups and range scans with bounded tree depth. Page splits, index size, random I/O, and write amplification influence performance. An index helps only when its ordering and selectivity match the query.

LSM-tree storage buffers writes, flushes sorted files, and compacts them over time. This can improve write throughput but introduces read amplification and background compaction I/O. Bloom filters and block caches reduce unnecessary reads. Write amplification measures physical bytes written relative to logical writes; compaction can become a latency bottleneck during sustained ingestion.

A write-ahead log records changes before modified data pages are considered durable, supporting crash recovery. Actual durability still depends on flush settings, storage guarantees, and replication acknowledgment policy. Benchmark realistic mixed workloads rather than selecting a database based on a single throughput number.

Storage engine trade-offs
B-tree family: Ordered access and range scans
May incur page splits and random writes.
LSM family: Buffered writes and sorted immutable files
Compaction improves organization but consumes I/O.