Introduction

A database must perform two fundamental operations efficiently:

• Store new or updated data safely
• Find the required data quickly

Optimizing both operations simultaneously is difficult. A structure designed for predictable reads can require more work during writes. A structure designed for high write throughput can require additional work during reads and background maintenance.

B-Trees and Log-Structured Merge Trees, commonly called LSM-Trees, represent two important storage-engine approaches.

• B-Tree family: Maintains keys in page-oriented balanced structures and updates the relevant pages.
• LSM-Tree family: Buffers writes in memory, flushes sorted immutable files, and merges those files through background compaction.

Neither design is universally better. The correct choice depends on the workload's read-to-write ratio, key distribution, range-query requirements, update pattern, storage hardware, latency objectives, and operational capacity for background maintenance.

Prerequisites

What Is a Storage Engine?

A storage engine is the database component responsible for organizing, persisting, reading, updating, and recovering stored data.

Application
    |
    v
Database API or query layer
    |
    v
Query execution
    |
    v
Storage engine
    |
    +-- Memory structures
    +-- Indexes
    +-- Transaction log
    +-- Data files
    +-- Cache
    +-- Recovery logic
    |
    v
Persistent storage

The storage engine influences:

• Write throughput
• Point-read latency
• Range-scan performance
• Space utilization
• Read and write amplification
• Background I/O
• Crash recovery
• Deletion behaviour
• Storage-device endurance

What Is a B-Tree?

A B-Tree is a balanced search tree in which each node can contain several sorted keys and child references.

                    [40 | 80]
                   /    |     \
                  /     |      \
                 v      v       v

          [10 | 20] [50 | 60] [90 | 100]

The tree remains balanced, meaning leaf nodes remain at the same depth. A high branching factor allows one node or storage page to direct searches across a large key range.

B-Tree Components

B+ Tree

Many database systems use a B+ Tree variation. Internal nodes guide navigation, while leaf pages contain record information and are commonly linked for ordered scanning.

Internal pages:

                 [40 | 80]
                /    |     \
               v     v      v


Leaf pages:

[10, 20, 30] <-> [40, 50, 60] <-> [80, 90, 100]

Linked leaf pages make ordered range scans practical after the database locates the first matching key.

B-Tree Read Path

A point lookup starts at the root and follows the key ranges until reaching the appropriate leaf page.

Find key 52

Root page:

[40 | 80]

52 is between 40 and 80
      |
      v
Middle child page:

[45 | 50 | 52 | 60]
      |
      v
Key 52 found

If upper tree levels and frequently accessed leaves remain in the page cache, many reads can avoid physical storage access.

B-Tree Write Path

An insert or update finds the relevant page, modifies it in memory, and eventually persists the changed page according to the database's durability mechanism.

Application writes key 52
        |
        v
Write recovery information
to transaction log
        |
        v
Navigate to target leaf page
        |
        v
Modify page in memory
        |
        v
Persist changed page
according to storage-engine policy

If the target page has no space, the engine can split the page and update parent routing information.

Page Split

Before insert:

[10 | 20 | 30 | 40]


Insert:

25


Page is full


After split:

[10 | 20]     [25 | 30 | 40]
       \       /
        \     /
      Parent updated

Splits can propagate upward when a parent page also lacks space.

B-Tree Range Scan

B-Trees naturally maintain key ordering.

Query:

Keys from 40 through 75


Steps:

1. Navigate to first key greater than or equal to 40.
2. Read matching records in key order.
3. Continue through neighboring leaf pages.
4. Stop after key 75.

This makes B-Tree-family structures suitable for ordered indexes, prefix ranges, date ranges, and pagination using indexed keys.

What Is an LSM-Tree?

LSM means Log-Structured Merge. An LSM-Tree accepts new writes into an in-memory sorted structure and later flushes the accumulated data to immutable sorted files on persistent storage.

Write request
      |
      +-- Write-Ahead Log
      |
      v
Active Memtable
      |
      v
Immutable Memtable
      |
      v
Flush
      |
      v
Level 0 SST files
      |
      v
Background compaction
      |
      v
Lower-level SST files

These immutable sorted disk files are commonly called SSTables or sorted runs.

LSM-Tree Components

LSM-Tree Write Path

Application writes key 52
        |
        v
Append write to WAL
        |
        v
Insert key into active memtable
        |
        v
Acknowledge according to durability policy
        |
        v
Memtable becomes full
        |
        v
Freeze memtable
        |
        v
Flush sorted contents to SSTable
        |
        v
Compact files in background

The incoming write does not need to locate and immediately rewrite its final on-disk position. The engine buffers many writes and writes them in sorted batches.

Memtable

A memtable is the active in-memory data structure receiving new writes.

Active memtable:

10 -> value A
20 -> value B
35 -> value C
52 -> value D
90 -> value E

The memtable maintains ordered keys so it can be flushed as an ordered on-disk structure.

Because memory is volatile, a durable LSM implementation commonly records writes in a write-ahead log before relying on the memtable.

SSTable

An SSTable is an immutable file containing keys in sorted order.

SSTable A:

10 -> value A
20 -> value B
35 -> value C
52 -> value D
90 -> value E

After an SSTable is created, its existing contents are not normally updated in place. Newer values are written to newer structures.

LSM-Tree Read Path

A point read must locate the newest visible value across memory and one or more disk files.

Read key 52
    |
    v
Check active memtable
    |
    +-- Found:
    |      return newest visible value
    |
    +-- Not found:
           check immutable memtables
                |
                v
           check recent SSTables
                |
                v
           check lower levels
                |
                v
           return newest matching value
           or not found

The engine uses file metadata, indexes, caches, and Bloom filters to avoid searching every stored key.

Bloom Filters

A Bloom filter is a space-efficient probabilistic structure used to test whether a key might exist in a file.

Check Bloom filter for key 52
        |
        +-- Definitely absent:
        |      skip this SSTable
        |
        +-- Might exist:
               inspect this SSTable

A standard Bloom filter can return a false positive, meaning that it says a key might exist when the key is absent. It should not return a false negative for an item inserted into a correctly functioning filter.

Compaction

Compaction merges sorted files into new sorted files.

SSTable A:

10 -> value A1
30 -> value C1
50 -> value E1


SSTable B:

20 -> value B2
30 -> value C2
60 -> value F2


Compaction output:

10 -> value A1
20 -> value B2
30 -> value C2
50 -> value E1
60 -> value F2

During compaction, the engine can discard older overwritten versions when those versions are no longer required by snapshots, transactions, or recovery rules.

Compaction helps:

• Reduce the number of sorted runs inspected during reads
• Remove obsolete overwritten values
• Reclaim deleted data when safe
• Reduce space amplification
• Maintain the selected level or tier organization

Leveled Compaction

In leveled compaction, disk files are organized into levels with controlled size targets.

Level 0:

Recently flushed files
Keys can overlap


Level 1:

Larger sorted level
Ranges are controlled


Level 2:

Larger again


Level 3:

Largest and older data

When a level exceeds its configured target, selected files are merged with overlapping ranges in the next level.

General Benefit

Controlled overlap can reduce the number of files that a point read must inspect in lower levels.

General Cost

Existing data can be rewritten repeatedly as it is compacted through the levels.

Tiered Compaction

In a tiered strategy, several similarly sized sorted runs can accumulate before they are merged.

Tier:

Run A
Run B
Run C
Run D
  |
  v
Merge selected runs
  |
  v
Larger run

Allowing more runs can reduce immediate merge work, but reads and temporary storage usage can increase.

Compaction-strategy Comparison

Actual results depend on the database, configuration, key distribution, update workload, value size, and storage hardware.

Deletions and Tombstones

SSTables are immutable, so an LSM-Tree cannot immediately remove an older key from every existing file.

Instead, the engine writes a deletion marker commonly called a tombstone.

Older SSTable:

course-42 -> published course data


Newer structure:

course-42 -> TOMBSTONE


Read result:

Key is treated as deleted.

Compaction later removes the tombstone and older values when it is safe to do so.

B-Tree vs LSM-Tree

Amplification

Storage-engine analysis commonly examines three forms of amplification:

• Write amplification
• Read amplification
• Space amplification

Write Amplification

Write amplification measures how much physical storage writing occurs compared with the logical data written by the application.

\[ WriteAmplification = \frac{ PhysicalBytesWritten }{ LogicalBytesWritten } \]

B-Tree Sources

• Write-ahead or recovery log
• Modified data or index page
• Page split
• Parent-page update
• Database-specific full-page or checkpoint behaviour

LSM-Tree Sources

• Write-ahead log
• Memtable flush
• Repeated compaction across levels or tiers
• Index and metadata updates

Read Amplification

Read amplification describes the additional storage work required to satisfy a logical read.

\[ ReadAmplification = \frac{ PhysicalDataRead }{ LogicalDataRequested } \]

A B-Tree lookup follows a small number of tree pages. An LSM point lookup can inspect memory and several candidate SSTables.

LSM implementations reduce read amplification using:

• Bloom filters
• Per-file key-range metadata
• Sparse indexes
• Block indexes
• Block cache
• Leveled organization
• Compaction

Space Amplification

Space amplification compares physical storage consumption with the logical live dataset.

\[ SpaceAmplification = \frac{ PhysicalStorageUsed }{ LogicalLiveDataSize } \]

LSM-Trees can temporarily retain older versions, tombstones, overlapping files, and compaction outputs. B-Tree engines can have partially filled pages, obsolete row versions, free space, and database-specific maintenance overhead.

The Amplification Trade-off

More aggressive LSM compaction:

- Fewer files to inspect
- Better controlled space usage
- More background rewriting


Less aggressive LSM compaction:

- Less immediate rewriting
- More sorted runs
- More possible read work
- More temporary duplicate data

Storage engines balance read, write, and space amplification rather than minimizing all three independently.

Point-read Comparison

B-Tree

Root
  |
  v
Internal page
  |
  v
Leaf page
  |
  v
Record

LSM-Tree

Memtable
  |
  v
Immutable memtable
  |
  v
Recent SSTables
  |
  v
Lower-level SSTables
  |
  v
Newest visible record

Caches and Bloom filters can make many LSM reads efficient, but the underlying read path has more possible locations to consider.

Range-scan Comparison

B-Tree Range Scan

Find first key
      |
      v
Read ordered leaf entries
      |
      v
Continue through adjacent leaves
      |
      v
Stop after end key

LSM Range Scan

Read matching memtable range
      |
      +-- Matching SSTable range A
      +-- Matching SSTable range B
      +-- Matching SSTable range C
      |
      v
Merge sorted iterators
      |
      v
Apply newest-version and tombstone rules
      |
      v
Return ordered result

Compaction style, overlapping files, cache state, scan width, and key distribution strongly affect LSM range-scan performance.

Write-latency Behaviour

LSM writes commonly have a short foreground path followed by background flushing and compaction.

Foreground:

WAL + memtable


Background:

Flush + compaction

This separation can provide high write throughput, but background work eventually must keep pace with incoming data.

Write Stalls

If flushing or compaction cannot keep up, the engine can accumulate too many immutable memtables or level-zero files.

Incoming write rate increases
        |
        v
Memtables fill faster
        |
        v
More SSTables reach Level 0
        |
        v
Compaction falls behind
        |
        v
Read amplification increases
        |
        v
Engine slows or stalls writes
to let background work catch up

Monitoring only foreground write latency can miss the growing compaction backlog that precedes a stall.

Latency Variability

Both designs can experience latency variation, but the causes differ.

Evaluate median and high-percentile latency under sustained workloads rather than relying only on average latency.

Caching

B-Tree Cache

A B-Tree page cache can retain root, internal, index, and frequently accessed leaf pages.

Page cache:

Root page
Hot internal pages
Frequently accessed leaves
Recently accessed data pages

LSM Cache

An LSM implementation can use several memory structures.

Memory:

Active memtable
Immutable memtables
Block cache
Index blocks
Bloom filters
File metadata

Storage-engine comparisons should include realistic cache sizes and warm-up conditions.

Crash Recovery

Both designs can use write-ahead logging, although their complete recovery procedures differ.

Conceptual B-Tree Recovery

Committed log records
      |
      v
Recover page-oriented changes
      |
      v
Restore transactionally valid state

Conceptual LSM Recovery

Existing SSTables remain present
      |
      v
Replay required WAL records
      |
      v
Rebuild lost memtable state
      |
      v
Resume flushing and compaction

Durability is determined by the database's acknowledgment and logging configuration, not by the tree name alone.

Updates and Multiple Versions

B-Tree Direction

Locate page containing key
      |
      v
Update record or record reference
      |
      v
Persist changed page
according to engine policy

LSM Direction

Older value remains in SSTable
      |
      v
Newer value written to memtable
      |
      v
Read returns newest visible version
      |
      v
Compaction later removes obsolete value

Snapshot isolation and multi-version concurrency can retain older versions longer in either database family.

Secondary Indexes

Secondary indexes introduce additional write and storage work regardless of the engine family.

Base record write
      |
      +-- Primary structure update
      +-- Secondary index 1 update
      +-- Secondary index 2 update
      +-- Secondary index 3 update

In a B-Tree-oriented engine, each index can involve page-oriented updates. In an LSM-oriented engine, each index can have its own memtable, SSTables, compaction, cache, and write amplification.

Write-heavy Workloads

LSM-oriented engines are often considered for workloads with sustained ingestion or many inserts and updates.

Examples include:

• Activity streams
• Telemetry
• Event ingestion
• Time-series data
• Large distributed key-value workloads
• Ingestion-heavy analytical pipelines

The complete workload still matters. Heavy updates and deletes can generate tombstones and substantial compaction work.

Read-heavy Workloads

B-Tree-oriented engines are often a natural fit when the workload emphasizes predictable point lookups, ordered scans, relational indexes, and frequent reads.

Examples include:

• Transactional application lookups
• Indexed account and order retrieval
• Ordered pagination
• Frequent range queries
• Workloads with several relational indexes

An LSM engine can also serve read-heavy applications when properly compacted, indexed, cached, and configured. The choice must be benchmarked rather than inferred only from a general rule.

Selection Guidance

Benchmarking Requirements

Do not benchmark only one read or one insert.

A realistic evaluation should include:

• Expected dataset size
• Realistic key and value sizes
• Expected read-to-write ratio
• Insert, update, and delete mix
• Point reads
• Range scans
• Existing secondary indexes
• Working-set size
• Cache size
• Concurrent clients
• Sustained test duration
• Compaction or checkpoint activity
• Storage-device characteristics
• Failure and restart behaviour

Important Measurements

• Read throughput
• Write throughput
• Median latency
• High-percentile latency
• Physical bytes read
• Physical bytes written
• Database size
• Cache hit rate
• Compaction or checkpoint backlog
• Write-stall duration
• CPU utilization
• Temporary storage requirement

Monitoring a B-Tree-oriented Engine

Monitor:

• Page-cache hit rate
• Logical and physical reads
• Page splits
• Index fragmentation or free-space behaviour
• Checkpoint activity
• Transaction-log growth
• Index usage
• Lock or latch waits
• Storage read and write latency
• Database and index size

Monitoring an LSM-oriented Engine

Monitor:

• Memtable size and count
• Flush rate
• Level-zero file count
• Compaction queue and pending bytes
• Compaction read and write throughput
• Write amplification
• Read amplification
• Space amplification
• Bloom-filter usefulness
• Block-cache hit rate
• Tombstone count
• Write stalls
• Per-level storage size
• Background-thread saturation

Alert Conditions

For B-Tree-oriented storage, alert when:

• Page-cache hit rate decreases unexpectedly
• Storage read latency increases
• Page splits or index growth increase sharply
• Transaction-log or checkpoint pressure grows
• Lock or latch waits exceed the objective

For LSM-oriented storage, alert when:

• Level-zero file count approaches the stall threshold
• Compaction cannot keep pace with incoming writes
• Pending compaction bytes grow continuously
• Write stalls occur
• Read amplification increases
• Tombstone-heavy reads become slow
• Temporary compaction space becomes insufficient

Troubleshooting Slow Reads

B-Tree Checklist

1. Verify that the query uses the intended index.
2. Inspect the query plan.
3. Check page-cache effectiveness.
4. Check storage read latency.
5. Check table and index statistics.
6. Check range selectivity.
7. Check lock and latch waits.
8. Check whether the query reads many non-covering data pages.

LSM-Tree Checklist

1. Check the active and immutable memtables.
2. Check the number of candidate SSTables.
3. Check Bloom-filter and block-cache behaviour.
4. Check level-zero file count.
5. Check compaction backlog.
6. Check tombstone density.
7. Check whether the range touches several overlapping files.
8. Check storage bandwidth consumed by compaction.

Troubleshooting Slow Writes

B-Tree Checklist

1. Check transaction-log latency.
2. Check page splits.
3. Check the number of maintained secondary indexes.
4. Check lock and latch contention.
5. Check checkpoint and page-flush pressure.
6. Check storage random-write latency.
7. Check whether keys create an insertion hotspot.

LSM-Tree Checklist

1. Check WAL latency.
2. Check memtable flush rate.
3. Check immutable-memtable backlog.
4. Check level-zero file count.
5. Check compaction throughput.
6. Check write stalls and throttling.
7. Check storage free space for compaction.
8. Check whether secondary indexes multiply the write load.

Common LSM-Tree and B-Tree Mistakes

Recommended Test Cases

Best Practices

Practice Exercise

Compare B-Tree-oriented and LSM-Tree-oriented storage for the activity system of your online learning platform.

Requirements

1. Generate course and learner activity records.
2. Use realistic tenant, course, learner, and event keys.
3. Test sequential event ingestion.
4. Test random learner-progress updates.
5. Test point lookup by activity ID.
6. Test activity retrieval for one learner.
7. Test activity retrieval over a date range.
8. Test deletion of expired activity records.
9. Add one secondary access path.
10. Measure write throughput.
11. Measure point-read and range-scan latency.
12. Measure high-percentile latency.
13. Measure physical bytes read and written.
14. Observe page splits or compaction activity.
15. Observe performance after the dataset exceeds memory.
16. Test restart and recovery.
17. Document which engine better satisfies each access pattern.

Comparison Template

Frequently Asked Questions