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.
Ordered access and range scansBuffered writes and sorted immutable files