B-Tree vs LSM-Tree: The Storage-Engine Tradeoff Behind Every Database You Use

Every relational database architecture is built upon a fundamental design commitment: optimizing for either read efficiency or write throughput. This decision is implemented at the storage engine layer through one of two primary data structures: the B-tree or the Log-Structured Merge-tree (LSM-tree). These structures dictate how data is persisted, indexed, and retrieved, effectively defining the system's performance characteristics before a single query is executed.

B-Trees (Read-Optimized)

B-trees update data in place, overwriting specific leaf nodes to maintain a sorted tree structure. Because a key exists in exactly one location, reads follow a singular path from root to leaf, making them ideal for point lookups.

• Advantage: Exceptional read performance due to deterministic key location.
• Tradeoff: High write latency under load, as the engine must perform random disk I/O to update nodes and frequently rebalance the tree via page splits.
• Examples: PostgreSQL, MySQL (InnoDB).

LSM-Trees (Write-Optimized)

LSM-trees treat writes as sequential appends to memory (memtables), which are later flushed to immutable files on disk. This architecture avoids random writes by transforming them into sequential disk operations.

• Advantage: High ingestion throughput, making them suitable for time-series data or logging.
• Tradeoff: Read amplification. A single key may reside across multiple files, requiring lookups to check several locations. Compaction—the background process of merging these files—is CPU and I/O intensive; if write volume outpaces compaction, latency can degrade exponentially.
• Examples: Cassandra, RocksDB, HBase.

Engineers often encounter friction when using a B-tree-backed RDBMS for write-heavy workloads, such as rapid event logging. Understanding this storage-level bet is critical; systems like MySQL’s MyRocks engine demonstrate that engineers can sometimes swap the underlying storage engine—replacing InnoDB’s B-tree with an LSM-tree—to align the database architecture with specific workload demands without altering the relational interface.

B‑trees store rows in a hierarchy of fixed‑size pages that remain sorted at all times. When a INSERT or UPDATE occurs, the engine walks from the root node to the leaf page that should contain the target key, rewrites that leaf in place, and then propagates any necessary structural changes upward.

• In‑place updates: The leaf page is modified directly on disk (or in the buffer pool) rather than being copied elsewhere. This guarantees that the tree is always in a consistent, fully sorted state.
• Single‑path reads: A point lookup follows exactly one path from root to leaf. Because each key exists in only one location, the read never needs to search multiple structures.
• Balanced depth: When a leaf fills, it splits and the middle key is promoted to the parent. Rebalancing keeps all leaves at the same depth, ensuring O(log N) lookup cost even for billions of rows.

In practice, a PostgreSQL index on customer_id might look like this:

CREATE INDEX ON customers (customer_id);
SELECT * FROM customers WHERE customer_id = 12345;

The SELECT triggers a single traversal: root → internal node → leaf containing the row. No additional scans or merges are required, which is why traditional RDBMS such as PostgreSQL and MySQL’s InnoDB default to B‑tree indexes for read‑heavy, point‑lookup workloads.

Contrast this with log‑structured merge trees (LSM‑trees), which avoid in‑place writes by appending immutable files and later merging them. While LSM‑trees excel when write volume dominates, they introduce read amplification because a key may appear in several files and must be checked sequentially, even with Bloom filters. B‑trees avoid that overhead by guaranteeing a unique location for each key.

When designing a schema, consider the following checklist:

• Is the workload dominated by point reads? Prefer B‑tree indexes.
• Will updates frequently cause page splits? Monitor page‑split rates and adjust fill factors.
• Do you need strict ordering for range scans? B‑trees maintain sorted order naturally.

Understanding the in‑place update mechanism and the single‑path guarantee helps engineers predict latency, tune buffer pool sizes, and avoid unexpected write amplification in systems that rely on B‑tree storage.

Log-Structured Merge-trees (LSM-trees) optimize storage engines for high-ingest throughput by prioritizing sequential I/O over random writes. Unlike B-trees, which perform in-place updates and require costly random disk access to modify leaf pages, an LSM-tree buffers incoming data in an in-memory structure known as a memtable. Once the memtable reaches a capacity threshold, it is flushed to disk as an immutable sorted file, typically referred to as an SSTable (Sorted String Table).

This architecture decouples the write operation from the physical storage organization, enabling high write performance by converting random updates into sequential append operations. Systems such as Cassandra, RocksDB, and HBase utilize this approach to handle write-heavy workloads, such as event logging or time-series data, where ingest volume exceeds the capacity of traditional B-tree-backed RDBMS systems.

Engineering teams should note the following operational characteristics of LSM-based systems:

• Read Amplification: Because a single key may exist in the memtable or across multiple immutable files on disk, read operations must check several locations to locate the most recent version. Databases often mitigate this latency using Bloom filters to probabilistically skip files that do not contain the requested key.
• Compaction Overhead: The system must periodically merge smaller files into larger ones to reclaim space and discard superseded versions. This background process, known as compaction, consumes significant CPU and disk I/O.
• Backpressure: If compaction cannot keep pace with the ingest rate, the number of uncompacted files increases, causing read latency to spike. In extreme cases, the system must implement write throttling to allow the merge process to recover.

For applications experiencing write-side bottlenecks in legacy systems, transitioning to an LSM-optimized engine—or utilizing specialized storage engines like MyRocks—can prevent the performance degradation typically associated with excessive B-tree page rebalancing under sustained high-load conditions.

The performance profile of a database is fundamentally determined by how it balances the competing demands of storage layout and access patterns. The core architectural decision lies between B-Trees and Log-Structured Merge-Trees (LSM-Trees), each imposing distinct costs on either write operations or read latency.

B-Trees: Optimizing for Point Lookups
B-Trees are designed for read-heavy, point-lookup workloads, maintaining data in a strictly sorted, in-place structure. A write operation necessitates navigating from the root to a specific leaf page. Once the page is modified, it remains the sole authoritative location for that key. This predictability ensures that read operations follow a single, efficient path. However, B-Trees incur significant costs during writes:

• Disk Seeks: As datasets exceed available memory, updating a page requires a random I/O disk seek.
• Page Rebalancing: To maintain strict depth uniformity, the engine must split pages as they fill, creating overhead that grows under heavy concurrent write pressure.

LSM-Trees: Optimizing for Ingest Throughput
LSM-Trees prioritize write efficiency by treating updates as sequential appends. New data is buffered in a memory-resident memtable before being flushed to immutable files on disk. While this design avoids random in-place rewrites, it shifts the complexity to the read path:

• Fragmented Reads: A lookup must check multiple locations—the memtable and various disk-based files—to locate the most recent version of a key.
• Bloom Filters: To mitigate read latency, engines use Bloom filters, a probabilistic data structure that identifies if a key is definitely absent in a file, allowing the system to skip unnecessary disk I/O.
• Compaction Costs: LSM-Trees defer the merging of files to a background compaction process. This maintenance consumes significant CPU and I/O resources, potentially creating a performance spiral if write ingestion consistently outpaces the engine's ability to compact and consolidate data files.

For enterprise engineers, identifying the appropriate engine depends on the workload. Traditional relational databases like PostgreSQL and MySQL’s InnoDB utilize B-Trees for their read-side efficiency. Conversely, systems designed for high-volume event logging or time-series data, such as Cassandra or RocksDB, leverage the sequential write performance of LSM-Trees.

Log‑structured merge trees (LSM‑trees) defer most write work by appending new data to an in‑memory memtable and later flushing immutable SSTables to disk. This design eliminates random‑write seeks, which is why systems such as Cassandra, RocksDB, LevelDB, and HBase excel when ingest volume dominates the workload.

The hidden cost of this approach is compaction—the background process that merges overlapping SSTables, discards superseded key versions, and rewrites data into larger, sequential files. Compaction competes for the same CPU and I/O resources that live traffic consumes. When the write rate exceeds the rate at which the background thread can merge files, a compaction backlog forms.

Under a sustained write pressure the backlog triggers a cascade of degradations:

• Write amplification: each incoming write may cause additional flushes because the memtable fills more often.
• Read latency growth: lookups must probe every un‑compacted SSTable; even with Bloom filters, the number of files to check rises, increasing CPU and I/O per read.
• Disk space pressure: overlapping files retain duplicate key versions until they are merged, inflating on‑disk size.
• Spiral effect: higher read latency and larger write amplification further stress the storage subsystem, making it harder for compaction to catch up.

Practical examples illustrate the failure mode. In a Cassandra cluster subjected to continuous event‑logging traffic, operators often observe a sudden jump in read latency at night when the compaction thread cannot keep pace with the write stream. Similarly, a RocksDB instance used for time‑series metrics may exhaust its allocated write‑amplification budget, leading to throttling of client writes.

Understanding this trade‑off is essential before selecting a storage engine. B‑tree engines (e.g., PostgreSQL, MySQL InnoDB) perform in‑place updates, paying at write time but keeping reads cheap and predictable. LSM‑tree engines shift the expense to the background, which is acceptable only when the system can guarantee sufficient CPU and I/O headroom for compaction under peak load.