LSM Trees vs. B-Trees: How Modern Databases Handle Reads and Writes

Step 4: Compaction

Over time, multiple SSTables accumulate.

Background compaction merges overlapping files, removes obsolete versions, and discards deleted records.

This keeps the storage engine manageable while preserving efficient lookups.

Why LSM Trees Are Extremely Fast for Writes

Imagine receiving one million sensor readings every minute.

A B-Tree would continuously modify existing pages.

An LSM Tree simply keeps appending new records.

Sequential disk writes are much faster than scattered random writes, particularly on traditional hard drives and still beneficial on SSDs.

This is why many write-heavy systems choose LSM Trees.

Examples include:

• Cassandra
• RocksDB
• LevelDB
• ScyllaDB
• HBase

These databases are optimized for continuous ingestion rather than complex analytical queries.

Reads Become More Complicated

The trade-off appears during reads.

Suppose a key exists.

Where should the database look?

It may be:

• In the MemTable.
• In the newest SSTable.
• In an older SSTable.
• In an even older SSTable.

Without optimization, every lookup could require checking multiple files.

To reduce unnecessary disk reads, LSM Trees use Bloom Filters.

A Bloom Filter quickly answers:

"This key definitely isn't here."

or

"This key might be here."

If the filter says the key cannot exist inside a particular SSTable, the database skips reading that file entirely.

Bloom Filters dramatically improve lookup performance while consuming very little memory.

The Hidden Cost of Compaction

Compaction is both the strength and weakness of LSM Trees.

Eventually, scattered SSTables must be merged.

During compaction the database:

• Reads existing files.
• Merges records.
• Removes duplicates.
• Deletes obsolete versions.
• Writes new SSTables.

Although this happens in the background, it consumes CPU, memory, and disk bandwidth.

Large compactions can temporarily increase latency if not managed carefully.

Modern databases devote significant engineering effort to scheduling compactions efficiently.

Range Queries: B-Tree Wins

Suppose an application needs:

SELECT \*  
FROM Orders  
WHERE CreatedAt BETWEEN ...

B-Trees excel.

Data already exists in sorted order.

The database finds the first matching key and scans forward sequentially.

LSM Trees can support the same query, but data may reside across multiple SSTables created at different times. The engine often performs additional merging during reads, making large range scans more expensive.

This is one reason relational databases remain popular for transactional business applications.

Write Throughput: LSM Tree Wins

Now imagine an IoT platform ingesting telemetry from five million devices.

Every second brings another flood of writes.

Random updates become the bottleneck.

Sequential appends become the advantage.

LSM Trees handle these workloads exceptionally well because they transform random writes into sequential disk operations.

Applications involving:

• Logging
• Metrics
• Time-series data
• Event ingestion
• Social activity feeds

often benefit from LSM-based storage engines.

Space Amplification vs Write Amplification

Neither data structure is free.

B-Trees primarily pay the cost during updates.

LSM Trees pay the cost later through compaction.

Engineers describe these trade-offs using three concepts:

• Read amplification
• Write amplification
• Space amplification

Read amplification measures how many disk reads are required for one logical read.

Write amplification measures how much physical writing occurs for one logical write.

Space amplification measures how much additional storage is consumed beyond the actual dataset.

B-Trees generally have lower read amplification.

LSM Trees generally achieve higher write throughput but incur greater write amplification because data is rewritten during compaction.

Understanding these trade-offs is far more useful than memorizing which database uses which structure.

Which Databases Use Which?

B-Tree Based

• PostgreSQL
• MySQL (InnoDB)
• SQLite
• Oracle Database
• SQL Server

These databases prioritize predictable reads, indexing, and transactional workloads.

LSM Tree Based

• Cassandra
• RocksDB
• LevelDB
• ScyllaDB
• HBase

These systems prioritize sustained write performance and horizontal scalability.

Choosing the Right Storage Engine

A common system design mistake is choosing databases based only on popularity.

Instead, start with workload characteristics.

Ask questions like:

• Is the system read-heavy or write-heavy?
• Are range scans common?
• Is data mostly append-only?
• Are updates frequent?
• Is write latency more important than read latency?

The answers often determine whether a B-Tree or LSM Tree is the better foundation.