Log-structured Merge Tree

SUMMARY

A Log-structured Merge Tree (LSM tree) is a storage structure that optimizes write-intensive workloads by converting random writes into sequential ones. It maintains multiple levels of sorted data, periodically merging them to balance write throughput with read performance.

How LSM trees work

LSM trees organize data into multiple levels, with each level increasing in size but decreasing in access frequency. New writes first go to an in-memory buffer (MemTable), which is periodically flushed to disk as immutable files (SSTables or Sorted String Tables).

When a level reaches its size threshold, a background process merges it with the next level, maintaining sorted order. This process, called compaction, helps manage space and improve read performance.

Next generation time-series database

QuestDB is an open-source time-series database optimized for market and heavy industry data. Built from scratch in Java and C++, it offers high-throughput ingestion and fast SQL queries with time-series extensions.

Try live demo Read documentation

Performance characteristics

Write optimization

LSM trees excel at high-volume ingestion by converting random writes into sequential ones, making them ideal for time-series databases. The write amplification is managed through careful compaction strategies.

Read patterns

While writes are optimized, reads may need to check multiple levels, potentially affecting latency. Common optimizations include:

Bloom filters to skip unnecessary file checks
Caching frequently accessed data
Zone maps for efficient range queries

Space efficiency

LSM trees achieve good compression ratios because:

Data is stored in sorted, immutable files
Compaction removes duplicates and obsolete values
Each level can use different compression strategies

Next generation time-series database

Try live demo Read documentation

Applications in time-series data

LSM trees are particularly well-suited for time-series workloads because:

Time-series data is often write-once, read-many
Newer data is accessed more frequently than older data
Data naturally aligns with the leveled structure (hot/warm/cold)

For example, in financial market data:

Tradeoffs and considerations

Advantages

Excellent write performance
Good compression ratios
Natural support for time-based partitioning

Challenges

Read amplification during queries
Background compaction overhead
Complexity in tuning level sizes and merge policies

When implementing LSM trees, organizations must balance these factors based on their workload characteristics and performance requirements.

Practical implementation

Modern databases using LSM trees often employ:

Multiple MemTables for write buffering
Concurrent compaction strategies
Intelligent cache eviction policies
Flexible compaction strategies

The storage engine configuration significantly impacts performance:

LSM trees continue to evolve with innovations in storage technology and changing application requirements, making them a cornerstone of modern high-performance databases.