LSM-Trees vs B-Trees: Read Paths, Write Amplification, and the Storage Engine Tradeoffs Under Your App

Data Systems

Most applications eventually learn the same uncomfortable truth: writing data safely and finding it quickly are different engineering problems.

That sounds obvious, but it is easy to underestimate how much product behavior depends on the storage engine's answer.

When a user clicks Save, the system needs a durable write path. When that same user opens a dashboard, searches an order, refreshes a timeline, or retries a payment, the system needs a fast read path. The shape of those paths is heavily influenced by the structures sitting underneath the database API.

This article explains two of the most important families of storage engines from modern databases: log-structured storage, which leads to LSM-trees, and page-oriented update-in-place storage, which leads to B-trees. Both solve the same core problem. They just optimize different parts of it.

For frontend and JavaScript engineers, this is not backend trivia. These tradeoffs are often the hidden reason a write path is smooth but reads are eventually consistent, or a search endpoint is fast but updates create bursty latency, or a local embedded database behaves differently from a networked service.

The Simplest Database Is Fast to Write and Terrible to Read

Start with the smallest possible mental model.

Imagine a database that stores each new key-value pair by appending one line to a file:

42,{"name":"San Francisco","attractions":["Golden Gate Bridge"]}
42,{"name":"San Francisco","attractions":["Exploratorium"]}

That write path is attractive because append-only writes are cheap.

  • no in-place overwrite,
  • no page split,
  • no need to shuffle records around to create space,
  • mostly sequential disk access.

This is the core intuition behind log-structured storage: treat the disk like an append-only log and keep adding new versions.

The problem is reads.

If the only way to find key 42 is to scan the file until the latest occurrence appears, lookup cost grows with the file size. What started as a wonderfully simple write path becomes an increasingly bad read path.

This is the first real storage-engine lesson: optimizing writes by itself is not enough. You need an indexing strategy that restores efficient retrieval.

Hash Indexes Help Point Reads, but Only Up to a Point

One improvement is to keep an in-memory hash map from key to byte offset in the append-only file.

When a new value is appended, the hash map is updated to point at the newest position. Reads can then jump directly to the latest record instead of scanning the whole log.

That fixes a lot.

It also leaves several problems behind:

  • old versions still occupy disk space until some cleanup happens,
  • the in-memory index must be rebuilt after restart unless it is persisted separately,
  • the hash table has to fit in memory,
  • range queries are poor because hashes are not ordered.

That last point matters more than many teams expect.

If your product only ever asks for one key at a time, a hash-based lookup is fine. But real systems often need queries like:

  • all orders from yesterday,
  • all invoices for one customer,
  • every event between two timestamps,
  • all sessions whose IDs fall into a shard range.

Range queries want order. Hashes do not provide it.

SSTables Add Order Back into the Picture

The next step is to store keys in sorted order. That leads to the Sorted String Table, usually shortened to SSTable.

An SSTable still stores key-value pairs on disk, but it adds two crucial constraints:

  • keys are written in sorted order,
  • each key appears at most once in a segment.

This opens the door to a sparse index.

Instead of holding every key in memory, the database can store the first key from each block of sorted data along with the block's byte offset. To find a key, the engine uses the sparse index to jump to roughly the right block, then scans only that small area.

That is a very different cost profile from scanning an entire append-only log.

It also makes range queries efficient. Once the engine finds the starting block, it can continue scanning forward through adjacent sorted data instead of performing many unrelated point lookups.

This is one reason sorted on-disk structures show up so often in database internals. Sorted data is not just convenient. It turns several awkward queries into straightforward sequential scans.

LSM-Trees Combine Fast Writes with Sorted Segments

If SSTables need sorted output, how do you accept writes in arbitrary order?

The usual answer is a hybrid design:

  1. New writes go into an in-memory ordered structure called a memtable.
  2. Once the memtable reaches a size threshold, it is flushed to disk as a sorted SSTable segment.
  3. Reads check the memtable first, then recent segments, then older ones.
  4. A background compaction process merges segments and discards overwritten or deleted values.

This family of designs is called an LSM-tree, short for log-structured merge-tree.

The name matters because the merge step is the entire game. Instead of updating one on-disk page in place, the engine keeps creating immutable sorted segments and later merges them into cleaner, larger segments.

That approach gives strong write throughput because the disk mostly sees large sequential writes.

It also explains a lot of the operational behavior engineers observe in systems such as RocksDB, Cassandra, ScyllaDB, HBase, and Lucene.

Compaction Is Both the Superpower and the Tax

Compaction is what keeps an LSM-based engine from drowning in stale data.

When multiple segments contain different versions of the same key, compaction merges them and retains only the newest value. If a key was deleted, the engine usually writes a tombstone first and removes older versions later during compaction.

This gives LSM systems several advantages:

  • writes stay append-friendly,
  • old immutable segments are easy to replicate and copy,
  • merges can happen in the background,
  • the engine can adapt compaction strategy to the workload.

But compaction is not free. It creates several kinds of amplification and variability:

  • the same logical write may be rewritten multiple times,
  • background merges consume disk bandwidth and CPU,
  • a lagging compaction queue can increase read cost,
  • some workloads experience latency spikes when flushing or compaction cannot keep up.

This is why an LSM engine can look excellent on write-heavy benchmarks and still feel temperamental if the compaction policy is poorly matched to the workload.

The product-level version of this is simple: a system can be healthy on average and still produce ugly outliers when maintenance work piles up behind user traffic.

Bloom Filters Reduce Wasted Reads

One subtle LSM problem is negative lookup cost.

If the key you want does not exist, the engine may need to check several segments before it can conclude that the key is absent. That gets expensive as segments accumulate.

This is where Bloom filters help.

A Bloom filter is a compact probabilistic structure that can answer one specific question quickly: could this key exist in this segment?

  • If the Bloom filter says no, the segment can be skipped.
  • If it says maybe, the engine still needs to check the segment.

That means Bloom filters trade a small amount of storage for fewer pointless reads. They do not prove presence. They cheaply rule out absence.

For applications, this often matters on miss-heavy workloads such as cache-like lookups, dedup checks, or APIs that frequently query keys that may not exist yet.

B-Trees Make a Different Bet: Update Pages In Place

The other dominant family of storage engines starts from a different assumption.

Instead of treating disk as a log of immutable segments, a B-tree treats disk as fixed-size pages. Keys are stored in sorted order within a tree of pages, and reads navigate that tree by following page references from root to leaf.

At a high level:

  • the root page routes the lookup into the right range,
  • internal pages refine the range,
  • leaf pages contain the value or a reference to it.

Because the tree stays balanced, lookup depth is usually small even for large datasets. A read often touches only a few pages.

If a page fills up during insert, it is split into two pages and the parent is updated with a new boundary key.

This structure is why B-trees are still the default index strategy in many relational databases and many storage engines that care about predictable point lookups and range scans.

B-Trees Usually Read Predictably and Write More Randomly

The B-tree tradeoff is almost the mirror image of an LSM-tree.

Because related keys are organized into a navigable tree of pages, reads are usually stable and predictable. Range scans are also natural because the keys are sorted.

Writes are more awkward.

If the key being updated lives on some page in the middle of the tree, the engine may need to overwrite that page in place. If a page split occurs, it may need to update multiple related pages. Historically this meant more random I/O than append-oriented designs.

Even on SSDs, where random access is far less disastrous than it was on spinning disks, the distinction still matters.

Many small overwrites produce different stress than a few large sequential writes. They affect write throughput, durability behavior, garbage collection inside SSDs, and how much internal rewriting the storage medium has to do.

That is why the old rule of thumb still mostly survives:

  • LSM-trees often favor write-heavy workloads.
  • B-trees often favor read-heavy workloads.

It is only a rule of thumb, but it is a useful one.

Durability Is Not the Same as Fast Writes

Both families still need crash recovery.

LSM engines usually keep a separate write-ahead log so the in-memory memtable can be reconstructed after a crash.

B-tree engines also use write-ahead logs because page updates are dangerous to apply directly without recovery support. If a crash happens mid-update, the engine must be able to restore a consistent tree.

This is one of the easiest mistakes to make when reasoning about storage: a fast in-memory write path is not durable until the relevant recovery data has been persisted.

That difference shows up at the application boundary as latency.

If a request is acknowledged only after the durable write has been recorded, the user experiences one latency profile. If the system acknowledges earlier and lets some work complete asynchronously, the UX may feel snappier but the failure model changes.

Storage-engine guarantees leak upward.

Write Amplification and Space Amplification Are Real Product Costs

One logical write from the application often becomes several physical writes underneath.

In LSM systems, data may be written:

  • to a durability log,
  • to the flushed SSTable,
  • again during one or more compaction passes.

In B-tree systems, data may be written:

  • to a write-ahead log,
  • to the tree page,
  • possibly to neighboring pages if splits or structural changes occur.

This is called write amplification.

It matters because the storage engine does not write business facts once. It writes a changing set of physical representations of those facts. Higher amplification means fewer logical writes per second for the same disk budget, and more wear on SSDs.

There is also space amplification.

LSM systems can temporarily keep multiple versions of data alive until compaction removes them. B-trees can accumulate fragmentation and free space inefficiencies over time.

From a product perspective, this affects cost, background maintenance behavior, and how quickly performance changes as the dataset grows.

Deletion Is Not Always Immediate Deletion

One of the more important operational details in log-structured systems is that deleting a record often means appending a tombstone and cleaning up later.

That is great for write efficiency.

It is less great if someone assumes that a delete becomes physical erasure immediately.

In many engines, especially LSM-based ones, the old bytes may remain in older segments until compaction rewrites them away. That lag matters for:

  • storage planning,
  • snapshot behavior,
  • backup retention,
  • compliance-sensitive deletion workflows.

This is a good example of why storage-engine knowledge matters beyond performance. The deletion semantics of the underlying engine can influence legal and privacy design, not just benchmark charts.

Embedded Engines and In-Memory Systems Change the Deployment Shape, Not the Tradeoffs

The storage-engine discussion is often taught as if it only matters for big networked databases.

It does not.

Embedded engines such as SQLite, RocksDB, LMDB, DuckDB, and others bring these same ideas into local applications, mobile apps, desktop tools, edge workers, and backend processes that want a database library instead of a database service.

That deployment choice changes a lot:

  • network hops disappear,
  • local disk behavior matters more,
  • application and storage engine share a process,
  • operational overhead drops.

But the storage tradeoffs still exist. A local-first app still benefits from predictable read latency. A sync engine still cares about write bursts and compaction. An offline cache still cares about key-range scans, index design, and durability.

The same is true for in-memory databases. Keeping the working set in RAM can make reads dramatically faster, but durability still needs a strategy, usually logging, snapshots, replication, or some combination of them.

RAM changes the economics. It does not eliminate the need to reason about storage behavior.

What This Means for Product Engineers

If you are building product features rather than storage engines, the practical question is not which acronym sounds more advanced. It is what workload you are forcing onto the engine.

Watch for these signals:

  • A write-heavy ingestion pipeline, event log, or metrics stream often aligns well with LSM-style storage.
  • A user-facing system with lots of point reads and predictable range lookups often aligns well with B-tree-style storage.
  • A workload with frequent negative lookups benefits from Bloom-filter-assisted segment skipping.
  • A workload with compliance-sensitive deletion should examine tombstone and compaction behavior carefully.
  • A system with bursty writes should be evaluated for flush and compaction latency spikes, not only average throughput.

For frontend engineers, these choices show up as stale reads, read-after-write expectations, search responsiveness, timeline freshness, retry safety, and how honestly the UI needs to communicate eventual consistency.

Conclusion

LSM-trees and B-trees both exist because databases need to store data durably and retrieve it efficiently. They just take different routes.

LSM engines optimize around append-friendly writes, immutable sorted segments, compaction, and probabilistic helpers such as Bloom filters. B-trees optimize around sorted pages, balanced navigation, and predictable lookups with in-place structural updates. Neither family is categorically better.

The important lesson is that storage engines are workload decisions. If your system writes constantly and can tolerate the maintenance cost of compaction, an LSM design may be a strong fit. If your system lives or dies on steady read latency and straightforward point queries, a B-tree may be the better default.

Once you understand that, a lot of database behavior stops feeling mysterious. It starts looking like the natural consequence of the storage engine's bet.