Why Did Modern Databases Abandon the B+ Tree? LSM Tree Explained

The Log-Structured Merge Tree, commonly called an LSM Tree, represents a fundamental shift in how modern databases organize data for writes and reads. Rather than immediately placing every update into its final sorted location on disk, an LSM Tree first collects changes in memory, writes them out in large ordered batches, and later reorganizes those batches in the background. This design choice has become increasingly popular in high-performance databases because it transforms a costly operation—random writes scattered across disk—into a more efficient one: sequential writes in organized batches.

The question in the title deserves careful interpretation. Modern databases have not universally abandoned B+ Trees; rather, they have recognized that different workloads benefit from different data structures. The LSM Tree represents a different set of trade-offs, one that is especially valuable when a system must handle many writes and can benefit from converting scattered updates into larger, more sequential operations.

This article explains the core components of an LSM Tree—the MemTable, SSTable, compaction process, and Bloom Filters—and shows how they work together to achieve efficient write performance. Understanding these pieces gives engineers the foundation to reason about when and why to choose an LSM-style approach over alternatives.

The Problem: Random Writes and Storage Efficiency​

To understand why LSM Trees exist, we must first understand the problem they solve.

Imagine a traditional database that stores records in key order using a tree structure like a B+ Tree. When a write request arrives to update the value associated with key user:42, the database must locate the relevant position in the tree and modify the appropriate node. This is a straightforward operation for a single update.

Now imagine thousands or millions of updates arriving for unrelated keys. The updates may be scattered across the entire key space:

Update key: 8  -> value: A
Update key: 3  -> value: B
Update key: 11 -> value: C
Update key: 5  -> value: D
Update key: 42 -> value: E
Update key: 2  -> value: F

From a logical perspective, each operation is simple: find one key and change one value. From a storage perspective, however, these operations are problematic. Each update may require the database to:

1. Locate a different position on disk
2. Read the current data at that position
3. Modify the data
4. Write the modified data back
5. Update any parent structures that maintain the tree's organization

This pattern is called random writing because the destination of each write is not necessarily adjacent to the destination of the previous write. When a storage device must repeatedly seek to different locations, it incurs significant latency. Modern solid-state drives and hard drives both perform better when data is written sequentially to adjacent locations.

Consider the performance difference:

• Random writes: 1,000 updates might require 1,000 separate disk seeks, each costing microseconds to milliseconds.
• Sequential writes: 1,000 updates batched into one sorted file might require a single sequential write operation, completing much faster.

An LSM Tree changes the timing and shape of that work. It does not insist that every update immediately reach its final sorted position. Instead, it uses a sequence of stages that convert many small, scattered updates into larger sequential operations.

The High-Level Architecture of an LSM Tree​

An LSM Tree can be understood as a collection of sorted components at different stages of their lifecycle. New data begins in memory. Older data exists in immutable files on disk. Background processing gradually combines those files into more consolidated representations.

A simplified flow looks like this:

Incoming writes (random order)
      |
      v
  MemTable (in-memory, sorted)
      |
      | flush when full or appropriate
      v
  SSTable on disk (immutable, sorted)
      |
      | compaction (background process)
      v
  Merged SSTables (reorganized, consolidated)

Each component has a focused responsibility:

• The MemTable accepts and organizes recent writes in memory in sorted order.
• The SSTable (Sorted String Table) stores a sorted, persistent batch of data on disk.
• Compaction merges and reorganizes those sorted files to maintain efficiency.
• A Bloom Filter helps determine whether a file definitely does not contain a requested key, avoiding unnecessary file reads.

These parts should not be viewed as separate tricks or optional features. They are coordinated pieces of one integrated design. The MemTable makes it possible to batch updates. SSTables make those batches persistent. Compaction prevents the collection of files from becoming unnecessarily fragmented and removes obsolete data. Bloom Filters reduce wasted lookup work by quickly eliminating files that cannot contain a requested key.

The MemTable: Collecting and Organizing Recent Writes​

The first destination for an incoming write is the MemTable, short for memory table. It is an in-memory data structure that holds recent key-value updates in sorted order.

Suppose a database receives these writes in this arrival order:

put key: 8  -> value: A
put key: 3  -> value: B
put key: 11 -> value: C
put key: 5  -> value: D

The requests arrived in a mixed order (8, 3, 11, 5), but the MemTable can represent them in key order:

3  -> B
5  -> D
8  -> A
11 -> C

The critical insight is that the database can accept writes in their arrival order while preparing a sorted batch for a later disk write. It does not need to place each key directly into its final on-disk location at the moment the request arrives. This separation of concerns—accepting writes in any order while organizing them for efficient storage—is central to the LSM Tree's design.

The MemTable also represents the newest view of the data. If the same key is written multiple times, the MemTable retains the latest update according to the database's rules. For example:

put account:7 -> pending
put account:7 -> active
put account:7 -> suspended

The in-memory representation treats the most recent update as the current value. The exact handling of versions and deletion markers depends on the implementation, but the general principle is that recent changes are gathered and organized before being written as a sorted file.

A MemTable cannot grow indefinitely. Once it reaches an appropriate size threshold or time-based condition, its contents are made immutable and prepared for a disk flush. At the same time, a new MemTable can begin receiving incoming writes. This allows the system to separate new activity from the batch that is being written to disk.

The benefit is clear: instead of three independent random disk updates, the system can write one ordered batch. The write pattern has been transformed from many small, scattered operations into a larger sequential operation.

MemTable Implementation Details​

In practice, MemTables are often implemented using balanced tree structures like Red-Black Trees or skip lists, which maintain sorted order while supporting efficient insertion. Some implementations use B+ Trees or other structures. The key requirement is that the structure supports:

1. Fast insertion of new key-value pairs
2. Efficient iteration in sorted order
3. Lookup of existing keys to support reads and updates

When a MemTable is flushed to disk, the database iterates through it in sorted order, writing the data sequentially to create an SSTable.

SSTables: Sorted Files on Disk​

An SSTable, or Sorted String Table, is a persistent file containing sorted key-value data. The name emphasizes its defining property: records are stored in sorted order by key.

When a MemTable is flushed, its ordered contents become an SSTable. For example, the MemTable we saw earlier becomes:

SSTable 1:
3  -> B
5  -> D
8  -> A
11 -> C

The file is not normally treated as a mutable collection that is edited in place for every future update. Instead, new updates are written into newer MemTables and later flushed into additional SSTables. This immutability is important: once an SSTable is written, it never changes. This property simplifies many aspects of the system, including crash recovery and concurrent access.

After several flushes, the disk may contain multiple SSTables:

SSTable 1 (oldest):
2  -> old value
6  -> value X
10 -> value Y

SSTable 2:
1  -> value A
6  -> value Z
9  -> value B

SSTable 3 (newest):
4  -> value C
12 -> value D

Each individual file is sorted, but the collection of files is not necessarily one globally sorted file. A key can appear in more than one SSTable because it may have been updated after an older version was flushed. For instance, key 6 appears in both SSTable 1 and SSTable 2 with different values.

This creates a straightforward write path: new data is appended as a new sorted file rather than requiring immediate random modification of every older file. However, it also creates a lookup challenge: when searching for a key, the system may need to consider the MemTable and multiple SSTables, usually giving priority to newer data.

SSTable File Format​

In practice, SSTables are not simple text files. They typically include:

1. Data blocks: The actual key-value pairs, often compressed
2. Index blocks: Pointers to data blocks for efficient seeking
3. Metadata: Information about the file's contents, key ranges, and compression
4. Bloom Filter: A probabilistic data structure for quick negative lookups
5. Footer: Pointers to the index and metadata locations

This structure allows the database to efficiently locate data within an SSTable without reading the entire file.

How Reads Work in an LSM Tree​

A lookup in an LSM-style system must determine the newest known value for a key. The conceptual search order is:

1. Check the active MemTable (most recent writes).
2. Check any recently immutable in-memory table that is awaiting persistence.
3. Check newer SSTables before older SSTables (respecting the order of creation).
4. Return the newest matching value found.
5. If a newer deletion marker exists, treat the key as deleted rather than returning an older value.

The exact internal organization can vary, but the principle is consistent: newer information must override older information.

For a key such as 6, the database may find:

SSTable 3: not present
SSTable 2: 6 -> value Z
SSTable 1: 6 -> value X

The newer entry, value Z, is the result. The older entry value X may remain in SSTable 1 until compaction removes or replaces it.

This is the fundamental trade-off introduced by the write strategy. The write path becomes well suited to batching and sequential operations, but the read path must coordinate information spread across memory and multiple files. LSM Tree components such as compaction and Bloom Filters help control that cost.

Read Performance Considerations​

In the worst case, a read might need to check:

• The active MemTable
• One or more immutable MemTables awaiting flush
• Multiple levels of SSTables (depending on the compaction strategy)

This can result in more disk seeks than a B+ Tree lookup, which typically requires only a few seeks to navigate from root to leaf. However, Bloom Filters and careful compaction strategies can significantly reduce the number of files that need to be checked.

Compaction: Merging Sorted Files​

Compaction is the process of merging SSTables into new, reorganized SSTables. It is the mechanism that gradually turns many smaller sorted files into a more consolidated representation. Compaction is essential to the LSM Tree design; without it, the number of files would grow unbounded, making reads increasingly expensive.

Consider two SSTables that need to be compacted:

SSTable A (older):
2  -> old-2
5  -> old-5
8  -> old-8

SSTable B (newer):
1  -> new-1
5  -> new-5
7  -> new-7

A compaction process can read both files in sorted order and produce a merged result:

Merged SSTable:
1  -> new-1
2  -> old-2
5  -> new-5
7  -> new-7
8  -> old-8

Because the system knows which file contains newer information, it can keep the newest version of a repeated key. In this example, new-5 replaces old-5 in the compacted output. The old entry old-5 from SSTable A is discarded.

Compaction can also eliminate obsolete information. If a key was updated several times, older values are no longer needed once the newer value has been safely represented in the reorganized files. Similarly, a deletion can be represented so that an older value is not accidentally returned in future reads.

The Compaction Process in Detail​

The compaction algorithm is conceptually similar to the merge step in merge sort:

1. Open both SSTables for reading
2. Initialize pointers to the first entry in each file
3. While both files have unread entries:
   a. Compare the keys at the current pointers
   b. Write the entry with the smaller key to the output
   c. If keys are equal, write the entry from the newer file
   d. Advance the pointer in the file from which we wrote
4. Write any remaining entries from the non-empty file
5. Close the input files and write the output file

Because both input files are sorted, this process reads them sequentially without random seeks. The output is also written sequentially. This preserves the LSM Tree's preference for sequential processing.

Compaction Strategies​

Different LSM Tree implementations use different compaction strategies:

• Leveled Compaction: Maintains multiple levels of SSTables, with each level containing files of similar size. Compaction moves files from one level to the next.
• Tiered Compaction: Accumulates SSTables at each level until reaching a threshold, then compacts all of them together.
• Size-Tiered Compaction: Compacts SSTables when the total size reaches a threshold.

Each strategy represents a different balance between write amplification (how many times data is rewritten) and read amplification (how many files must be checked during reads).

Why Compaction Matters to Reads​

Without compaction, every flush could create another SSTable. As the number of files grows, a lookup may need to check more places. Even if each file is individually organized, the overall lookup process can become more complicated and slower.

Compaction helps by combining files and reducing duplicated versions. It can improve the shape of the on-disk data by making related key ranges easier to process together. It also gives the database an opportunity to discard entries that have been superseded.

This creates a balance:

• Less compaction: Means less background write work immediately, but potentially more files and more lookup work.
• More compaction: Can produce more consolidated files, but it requires additional reading and writing.

The right balance depends on the workload and the implementation. The general lesson is that compaction is a central part of the design, not an optional cleanup task that can be ignored.

Bloom Filters: Avoiding Definite Misses​

A Bloom Filter is a compact probabilistic data structure used to answer a useful question about a key and an SSTable:

Is this key definitely not in this file?

A Bloom Filter can answer "definitely not present" or "possibly present." It cannot safely answer "definitely present" unless the system performs a real lookup. A positive result means the file may contain the key and should be checked. A negative result means the file can be skipped.

How Bloom Filters Work​

A Bloom Filter is a bit array of fixed size, typically a few kilobytes per SSTable. When an SSTable is created, the database:

1. Initializes a bit array of size m with all bits set to 0
2. For each key in the SSTable: a. Applies multiple hash functions to the key b. Each hash function produces an index into the bit array c. Sets the bit at each index to 1

When checking if a key might be in the SSTable:

1. Apply the same hash functions to the key
2. Check the bits at the resulting indices
3. If all bits are 1, the key might be present (possibly present)
4. If any bit is 0, the key is definitely not present

Example​

Suppose we have a Bloom Filter with 8 bits and 2 hash functions. We add keys apple and banana:

Initial:     00000000
After apple: 10100100 (hash functions point to indices 1, 2, 5)
After banana: 11101101 (hash functions point to indices 0, 2, 3, 5)
Final:       11101101

Now we check for key cherry (hash functions point to indices 1, 4):

Check indices 1 and 4 in 11101101
Index 1: 1
Index 4: 0
Result: Definitely not present (because index 4 is 0)

If we check for key apple (hash functions point to indices 1, 2, 5):

Check indices 1, 2, 5 in 11101101
Index 1: 1
Index 2: 1
Index 5: 1
Result: Possibly present (all bits are 1)

False Positives and False Negatives​

Bloom Filters have an important property:

• False positives: The filter may say a key is possibly present when it is not. This causes an extra file check but does not cause the database to miss a real value.
• False negatives: The filter never produces false negatives. If it says a key is definitely absent, the key is truly absent.

This asymmetry is crucial. The filter is an optimization for avoiding definite misses, not the final authority on whether a key exists.

Practical Impact​

For example, suppose a database wants to find key 42 across several SSTables. A Bloom Filter associated with one file may report that 42 is definitely absent. The database can avoid reading that file for this lookup, saving disk I/O. Another file's filter may report that 42 might be present, so the database checks the file itself.

This is valuable because an LSM Tree may contain multiple SSTables, and not every file is relevant to every key. Bloom Filters reduce unnecessary work by quickly rejecting files that cannot contain the requested key.

In typical workloads, Bloom Filters can reduce the number of unnecessary file reads by 90% or more, significantly improving read performance.

A Complete Write and Read Example​

Let's trace through a complete example to see how all the pieces work together.

Initial State​

The database starts with an empty MemTable and no SSTables.

Phase 1: Initial Writes​

The database receives these operations:

put 10 -> A
put 3  -> B
put 10 -> C
put 7  -> D

The MemTable organizes these in sorted order:

MemTable:
3  -> B
7  -> D
10 -> C

Note that the earlier value 10 -> A does not appear in the current MemTable state. The later update 10 -> C is the newest value known in the MemTable.

Phase 2: First Flush​

When the MemTable reaches its size limit, the database flushes it to disk, creating SSTable 1:

SSTable 1:
3  -> B
7  -> D
10 -> C

A new MemTable begins accepting new writes.

Phase 3: More Writes​

New writes arrive:

put 2  -> E
put 10 -> F
put 9  -> G

The new MemTable contains:

MemTable:
2  -> E
9  -> G
10 -> F

Phase 4: Second Flush​

The MemTable is flushed to disk, creating SSTable 2:

SSTable 2:
2  -> E
9  -> G
10 -> F

Now the disk contains two SSTables.

Phase 5: Read Operation​

A read request arrives for key 10. The database:

1. Checks the active MemTable: not found
2. Checks SSTable 2 (newer): found 10 -> F
3. Returns F as the result

Note that the database did not need to check SSTable 1 because it found the key in the newer SSTable 2.

Phase 6: Compaction​

Background compaction merges SSTable 1 and SSTable 2:

Compacted SSTable:
2  -> E
3  -> B
7  -> D
9  -> G
10 -> F

The old SSTables are deleted, and the new compacted SSTable replaces them.

Phase 7: Read After Compaction​

A read request arrives for key 10. The database:

1. Checks the active MemTable: not found
2. Checks the compacted SSTable: found 10 -> F
3. Returns F as the result

The read is now simpler because there is only one SSTable to check.

This example captures the complete lifecycle: updates arrive, memory batches them, sorted files are created, reads prioritize newer information, and compaction consolidates the result.

LSM Trees vs. B+ Trees: Different Trade-offs​

A B+ Tree and an LSM Tree both organize data for database access, but they emphasize different behaviors. Understanding the differences helps engineers choose the right structure for their workload.

B+ Tree Characteristics​

A B+ Tree is commonly understood as an ordered tree structure designed to support navigation through key ranges and updates within that structure. Key characteristics include:

• Immediate organization: Updates are placed directly into their final sorted position in the tree.
• In-place modification: Existing nodes are modified when data changes.
• Balanced structure: The tree maintains balance to ensure consistent performance.
• Range queries: Efficient support for queries like "find all keys between X and Y."
• Predictable read performance: Reads typically require a consistent number of disk seeks (logarithmic in the number of keys).

LSM Tree Characteristics​

An LSM Tree separates incoming writes from later on-disk organization. Key characteristics include:

• Deferred organization: Updates are accumulated in memory and organized later through compaction.
• Immutable files: Once written, SSTables never change.
• Batched writes: Many small updates become one larger sequential operation.
• Background compaction: Reorganization happens asynchronously.
• Variable read performance: Reads may need to check multiple files, but Bloom Filters can reduce this cost.

The Key Contrast​

The fundamental contrast is not that one structure is universally better. It is the contrast between immediate organization and deferred organization:

• A tree-oriented approach keeps the primary structure organized as updates happen.
• An LSM-oriented approach batches updates and performs more organization later through compaction.

This makes LSM Trees attractive when:

• The workload is heavily write-oriented
• Converting random writes into sequential writes is an important goal
• The system can tolerate background compaction work
• Batching many updates is more important than individual update latency

B+ Trees remain attractive when:

• Read performance must be highly predictable
• Range queries are common
• The workload is read-heavy or balanced
• Background compaction overhead is unacceptable

Practical Strengths of the LSM Approach​

The main strength of LSM Trees is their write organization. Incoming changes can be gathered in memory and flushed in sorted batches rather than immediately scattered across disk locations.

Other useful properties follow from the same design:

1. Batching​

Many small writes can become one larger operation. Instead of 1,000 individual random disk writes, the system can perform one sequential write of 1,000 sorted records. This can improve throughput by orders of magnitude.

2. Sequential Organization​

SSTable creation and compaction process ordered data sequentially. Modern storage devices (both SSDs and hard drives) perform significantly better with sequential access patterns than with random access.

3. Version Consolidation​

Compaction can remove older values that have been superseded. If a key was updated 10 times, only the newest value needs to be retained in the compacted output. This reduces storage overhead and improves read performance.

4. Read Filtering​

Bloom Filters can skip files that definitely do not contain a key. This reduces unnecessary disk I/O during reads, improving read performance even though reads may need to check multiple files.

5. Clear Lifecycle​

Data moves through a clear lifecycle: from an active MemTable to immutable SSTables and then through compaction. This clarity simplifies crash recovery, concurrent access control, and other system aspects.

6. Write Amplification Control​

While compaction does rewrite data, the amount of rewriting can be controlled through compaction strategy choices. Different strategies offer different balances between write amplification and read amplification.

Practical Costs and Questions​

An LSM Tree is not simply a faster replacement for every other index. It moves work from one part of the system to another, creating new challenges.

Before choosing an LSM-style design, engineers should ask:

1. Workload Characteristics​

• Is the workload heavily write-oriented?
• What is the ratio of writes to reads?
• Are updates typically to different keys or repeated updates to the same keys?
• What is the typical size of values?

2. Compaction Overhead​

• Is it acceptable for background compaction to read and rewrite data?
• How much CPU and disk bandwidth can be dedicated to compaction?
• What is the acceptable impact on foreground read and write latency?
• How should compaction be scheduled to avoid interference with critical operations?

3. Read Performance​

• How many SSTables may a lookup need to consider in the worst case?
• Is predictable read latency important?
• How important are range queries?
• Can Bloom Filters adequately reduce the cost of checking multiple files?

4. Data Organization​

• How should newer values override older values?
• How should deletions be represented until compaction removes obsolete data?
• What is the appropriate size for the MemTable?
• How many levels of SSTables should be maintained?

5. System Integration​

• How should compaction be scheduled alongside normal reads and writes?
• How much memory is appropriate for the MemTable and lookup metadata?
• How should crash recovery work with multiple in-memory and on-disk components?
• How should concurrent reads and writes be coordinated?

These questions are not implementation details to postpone. They describe the fundamental trade-off: the system gains a batched write path but must manage deferred organization and potentially more complicated reads.

Write Amplification and Read Amplification​

Two important metrics help evaluate LSM Tree performance:

Write Amplification​

Write amplification is the ratio of bytes written to disk to bytes written by the application. In an LSM Tree, data may be written multiple times:

1. First write: Application writes to MemTable
2. Second write: MemTable is flushed to SSTable
3. Third write (or more): SSTable is compacted and rewritten

If an application writes 1 GB of data and the system writes 5 GB to disk (including compaction), the write amplification is 5x.

Write amplification affects:

• Storage device wear (especially for SSDs with limited write cycles)
• Disk bandwidth consumption
• Overall system throughput

Read Amplification​

Read amplification is the number of disk reads required to satisfy a single read request. In an LSM Tree, a read might need to check:

• The active MemTable (in-memory, no disk read)
• One or more immutable MemTables (in-memory, no disk read)
• Multiple SSTables (disk reads required)

If a read requires checking 10 SSTables, the read amplification is 10 (or less if Bloom Filters eliminate some files).

Read amplification affects:

• Read latency
• Disk I/O consumption
• Overall system responsiveness

The Trade-off​

Different compaction strategies create different trade-offs:

• Aggressive compaction: Lower read amplification (fewer files to check) but higher write amplification (more rewriting).
• Lazy compaction: Lower write amplification (less rewriting) but higher read amplification (more files to check).

Engineers must choose the right balance for their workload.

A Mental Model to Remember​

A useful mental model is a mailroom analogy.

B+ Tree approach: Similar to delivering every letter directly to its final shelf as soon as it arrives. The shelf remains organized, but every delivery may require navigating to a different place. Each delivery is immediate but potentially slow.

LSM Tree approach: More like collecting incoming letters in a sorting room. The letters are sorted in batches, placed into labeled boxes, and later merged into larger, better-organized boxes. A quick checklist can tell the worker which boxes definitely do not contain a particular letter.

In this analogy:

• The sorting room is the MemTable
• The boxes are SSTables
• The process of combining boxes is compaction
• The checklist is the Bloom Filter
• The mail carrier is the background compaction process

This model explains both the appeal and the cost. The system can process arrivals in batches, improving throughput. However, it must periodically spend time reorganizing the boxes (compaction) and finding the newest version when several boxes contain related information (checking multiple files during reads).

Real-World Examples​

LSM Trees are used in many modern databases:

• RocksDB: A high-performance embedded key-value store developed by Facebook, built entirely on LSM Tree principles.
• LevelDB: An embedded key-value store developed by Google, which pioneered many LSM Tree techniques.
• Cassandra: A distributed database that uses LSM Trees for its storage engine.
• HBase: A distributed database built on top of HDFS that uses LSM Tree-like structures.
• SQLite4: An experimental version of SQLite that explored LSM Tree-based storage.

These systems have demonstrated that LSM Trees can provide excellent write performance and throughput for many real-world workloads.

Final Takeaways​

An LSM Tree is built around a deliberate shift in when storage organization happens. Instead of performing every update directly against a final on-disk structure, it first collects writes in a MemTable, flushes sorted data into SSTables, and uses compaction to merge those files later.

The central flow is:

random incoming writes
        |
        v
sorted in-memory batch (MemTable)
        |
        v
sorted on-disk file (SSTable)
        |
        v
compaction and consolidation

Bloom Filters support the read path by identifying files that definitely cannot contain a requested key. They do not prove that a key exists, but they can prevent unnecessary file checks.

The broader lesson is that data structures are choices about trade-offs. LSM Trees favor batching and sequential organization for writes, while accepting background compaction and a more distributed read path. B+ Trees and LSM Trees should therefore be compared in terms of workload behavior rather than slogans.

Understanding MemTables, SSTables, compaction, and Bloom Filters gives engineers the foundation needed to reason about this choice clearly. When a workload is write-heavy and can tolerate background reorganization, LSM Trees often provide superior performance. When reads must be highly predictable or range queries are common, B+ Trees or other structures may be more appropriate.

The question "Why did modern databases abandon the B+ Tree?" should therefore be understood as "Why do modern databases increasingly choose LSM Trees for write-heavy workloads?" The answer is that LSM Trees convert a costly operation—random writes—into a more efficient one: batched sequential writes. For the right workload, this trade-off is compelling.