# B-tree vs LSM tree > Choose a B-tree when point reads, ordered scans, and predictable read latency are central; choose an LSM tree when sustained write throughput justifies compaction and more complex reads. Both support ordered access, and the better choice depends on cache size, key distribution, storage hardware, and the engine's implementation. Source: https://sysround.com/compare/b-tree-vs-lsm-tree Updated: 2026-11-05 ## Side by side | | B-tree | LSM tree | |---|---|---| | Organization | Mutable, ordered pages; usually a B+ tree | Memory buffer plus immutable sorted files | | Write path | Update cached pages; flush dirty pages later | Buffer writes, flush sorted files, compact | | Point reads | Traverse one tree; upper levels often cached | Check memory and candidate files; filters help | | Range scans | Traverse ordered leaf pages | Merge ordered streams across files and memory | | Write amplification | Page writes, logging, and occasional splits | Logging, flushes, and repeated compaction | | Background work | Dirty-page flushing and page maintenance | Flushing and compaction can cause stalls | | Space reclamation | Page reuse and cleanup depend on engine | Obsolete versions and tombstones await cleanup | | Crash durability | Commonly WAL; acknowledgment policy matters | Commonly WAL; acknowledgment policy matters | ## The differences that matter B-tree-based databases usually use B+ trees, with records or record references in ordered leaf pages. Updates modify cached pages, which are persisted later. LSM trees collect updates in a memtable and flush them into immutable sorted files, turning scattered logical writes into batched storage writes. A B-tree lookup follows a single search path, often with its upper levels already in memory. An LSM lookup may check the memtable and several files to find the newest visible value. Bloom filters can avoid many unnecessary file reads for absent keys, but they do not eliminate version resolution or accelerate arbitrary range scans. Both structures support range queries. A B+ tree walks ordered leaf pages, although those pages are not necessarily physically contiguous. An LSM tree merges sorted streams and resolves duplicate keys, versions, and deletions. Compaction policy changes how much merging a read must do. LSM compaction trades background CPU, I/O, and temporary disk space for fewer files and obsolete versions. If compaction falls behind, read costs and disk usage can rise until writes are throttled or stalled. B-trees also incur maintenance and write amplification through page flushing, splits, and version cleanup, so neither structure has a universal cost advantage. ## Choose B-tree when - Your workload is dominated by point lookups and short ordered scans, with a tight read-latency target. - You need frequent indexed updates and want to avoid reading across multiple sorted runs. - The working set fits well in the buffer pool, making cached page updates effective. - A B-tree-based engine already provides the transactions, indexes, and operational tooling your application needs. ## Choose LSM tree when - You have sustained, high-volume writes spread across a dataset larger than memory. - Your workload benefits from buffering and batching writes, and the system has capacity for compaction. - You can use Bloom filters and caching to meet point-read targets while accepting additional read-path complexity. - You can tune and monitor compaction, reserve temporary disk space, and apply backpressure when ingestion exceeds sustainable capacity. ## Worked example: Choosing storage for a metrics ingestion service Suppose a metrics service ingests 100,000 samples per second, each with a 200-byte encoded key and value. That is 20 MB/s of logical data before replication, logging, indexes, or compaction. Queries usually scan one metric over a recent time interval, so a key ordered by tenant, metric, and timestamp supports bounded scans. An LSM engine is a reasonable starting point because it batches writes, but capacity planning must include compaction traffic and retention cleanup. Test with concurrent ingestion, scans, and expired-data removal. If the workload instead shifts toward frequent small reads and scattered updates under a strict latency target, benchmark a B-tree engine rather than assuming the original choice still wins. ## In the interview - Start with the workload: read/write rates, record sizes, key distribution, range-scan frequency, retention, and latency targets. A write percentage alone is not enough. - Describe one write and one read end to end, including the WAL, memory structures, durable files or pages, and cache misses. Explain when a successful write becomes durable. - For an LSM choice, expect questions about compaction backlog, write stalls, tombstones, and disk headroom. Explain how you detect overload and reduce ingestion before space runs out. - For a B-tree choice, expect questions about buffer-pool misses, random updates, page splits, and index maintenance. Explain how additional indexes increase write cost. - Keep storage layout separate from distributed guarantees. Neither structure determines replication, transaction isolation, or consistency; those require separate design decisions. ## Common mistakes - Saying B-trees are for reads and LSM trees are for writes without discussing caching, access patterns, or maintenance costs. - Claiming LSM writes are always cheaper because they are sequential, while ignoring compaction and write amplification. - Assuming LSM trees cannot support range scans, or that Bloom filters make range scans cheap. - Treating B-tree as synonymous with SQL and ACID, or LSM tree as synonymous with NoSQL and eventual consistency. ## Interview questions where it comes up - [Design a distributed key-value store](https://sysround.com/questions/design-key-value-store): The local storage engine determines how each replica handles durable writes, point reads, compaction, and disk capacity. - [Design a metrics monitoring system like Datadog](https://sysround.com/questions/design-metrics-monitoring-system): Sustained ingestion, time-ordered scans, and retention cleanup make storage layout and background maintenance important design choices. - [Design a URL shortener like Bitly](https://sysround.com/questions/design-url-shortener): The backing store must balance durable mapping creation with low-latency point lookups that miss the cache. - [Design a chat app like WhatsApp](https://sysround.com/questions/design-whatsapp): Persisting messages by conversation and sequence requires balancing write throughput with ordered history scans. ## FAQ ### Is a B-tree faster than an LSM tree? Neither is universally faster. B-trees often suit point reads and short scans, while LSM trees can benefit sustained write-heavy workloads through buffering and batching. Compare them with realistic cache sizes, data distributions, durability settings, and background maintenance enabled. ### Do LSM trees support range queries? Yes. Their files are sorted, so range queries merge ordered iterators from relevant files and memory. The cost depends on file overlap, compaction policy, and how many obsolete versions or tombstones must be processed. ### Can an LSM-tree database provide ACID transactions? Yes, an LSM-based engine can support ACID transactions. Atomicity, isolation, and durability depend on mechanisms such as transaction coordination, versioning, concurrency control, and durable logging, not just the index structure. A B-tree alone does not provide those guarantees either. ## Related concepts - [B-trees](https://sysround.com/concepts/b-tree) - [LSM trees](https://sysround.com/concepts/lsm-tree) - [Write amplification](https://sysround.com/concepts/write-amplification) - [Bloom filters](https://sysround.com/concepts/bloom-filter) - [Write-ahead log](https://sysround.com/concepts/write-ahead-log) --- SysRound (https://sysround.com) is an AI practice tool for system design interviews: a voice or typed AI interviewer, a shared whiteboard, then feedback on every skill and a model answer. Its feedback is AI-generated and can be wrong.