B-Trees vs LSM-Trees

Overview

B-Trees and LSM-Trees (Log-Structured Merge Trees) are two fundamental data structures used in database storage engines, each optimized for different workload patterns. B-Trees excel at read-heavy workloads with their balanced structure and in-place updates, while LSM-Trees optimize for write-heavy scenarios through append-only operations and delayed merging.

This architectural choice affects everything from query performance to storage requirements, making it one of the most important decisions in database design. Systems like PostgreSQL and MySQL use B-Trees, while Cassandra, RocksDB, and LevelDB use LSM-Trees.

graph TD
    A[Database Storage Engine] --> B[B-Trees<br/>Read-Optimized]
    A --> C[LSM-Trees<br/>Write-Optimized]
    
    B --> D[Balanced Structure<br/>In-place Updates<br/>Fast Reads]
    C --> E[Append-only Logs<br/>Periodic Merging<br/>Fast Writes]
    
    D --> F[PostgreSQL<br/>MySQL<br/>Oracle]
    E --> G[Cassandra<br/>RocksDB<br/>LevelDB]
    
    style A fill:#e1f5fe
    style B fill:#e1f5fe
    style C fill:#e1f5fe
    style D fill:#e1f5fe
    style E fill:#e1f5fe
    style F fill:#e1f5fe
    style G fill:#e1f5fe

B-Trees: Read-Optimized Structure

Architecture

B-Trees maintain a balanced tree structure where all leaf nodes are at the same depth, similar to a well-organized filing system where every drawer is at the same height. This balanced structure ensures that searching for any piece of data takes the same amount of time, regardless of where it’s located.

Key Characteristics:

B-Trees are balanced, meaning all paths from the root to any leaf node have the same length - like having a perfectly organized library where every book is exactly the same distance from the entrance. Keys are maintained in sorted order within nodes, making it easy to find what you’re looking for. In-place updates mean modifications happen directly in existing pages, like editing a document in place rather than creating a new copy. Data is organized in fixed-size pages (typically 4KB-16KB), similar to how books are organized in chapters of consistent length.

B-Tree Implementation

B-Tree implementation involves managing nodes that can contain multiple keys and pointers to child nodes. Think of it like a sophisticated filing system where each folder can contain multiple documents and references to other folders. The tree maintains its balance through careful insertion and deletion operations that may require splitting or merging nodes when they become too full or too empty.

Search operations navigate down the tree by comparing the target key with keys in each node, similar to following directions in a multi-level building. Insert operations find the appropriate leaf node and add the new key, potentially causing the node to split if it becomes too full. Deletion operations remove keys and may require merging nodes or redistributing keys to maintain balance.

B-Tree Performance Characteristics

Read Performance:

B-Trees excel at read operations due to their balanced structure. Single key lookups take logarithmic time, meaning even with millions of records, you only need to check a small number of levels. Range scans are highly efficient because the sorted order allows sequential access to adjacent records. Sequential access is particularly fast because data is stored in sorted order, making it ideal for operations that need to process data in order.

Write Performance:

Write operations in B-Trees are more complex due to the need to maintain balance. Insert and update operations require logarithmic time to find the correct location and potentially split nodes. Delete operations also take logarithmic time and may require merging nodes. Write amplification is moderate because updates may require rewriting entire pages, but this is generally manageable compared to LSM-Trees.

LSM-Trees: Write-Optimized Structure

Architecture

LSM-Trees use a multi-level structure with periodic merging, similar to how a busy office manages incoming mail. New items are first placed in an in-memory buffer (like an inbox), then periodically sorted and filed into permanent storage levels. This approach optimizes for write performance by batching operations and deferring the expensive work of organizing data until later.

Key Characteristics:

LSM-Trees are write-optimized, meaning they prioritize fast writes over fast reads. They use append-only operations, like writing in a journal where you never erase anything, just add new entries. Periodic merging consolidates data from multiple levels, similar to how you might periodically organize scattered papers into proper files. This design trades read performance for write performance, making them ideal for write-heavy workloads.

LSM-Tree Implementation

LSM-Tree implementation involves managing multiple levels of sorted data structures. Think of it like a multi-tier filing system where new documents go into a temporary inbox, then get periodically organized into permanent filing cabinets. The system maintains a memory table for fast writes, then flushes data to disk in sorted files called SSTables.

Compaction is the process of merging multiple SSTables into fewer, larger files, similar to periodically consolidating scattered documents into organized folders. This process removes duplicate entries and organizes data more efficiently, but it requires significant I/O operations. The system uses bloom filters to quickly determine if a key might exist in a particular SSTable, reducing unnecessary disk reads.

LSM-Tree Performance Characteristics

Write Performance:

• Insert: O(1) amortized (appends to memtable)
• Very high write throughput

Read Performance:

• Single key lookup: O(log n) worst case (check all levels)
• May require multiple disk seeks
• Bloom filters help reduce false lookups

Detailed Comparison

Write Amplification

B-Trees:

Original write: 1 page
Page split cascading up tree: 2-3 additional page writes
Total write amplification: 3-4x

LSM-Trees:

Initial write: 1x (write-ahead log, then memtable flush)
Each compaction down a level: about T rewrites (T is the size ratio, usually 10)
Total write amplification: often tens of times, spread over time

Space Amplification

B-Trees:

• Typically 1-2x due to page fragmentation
• Internal nodes reduce utilization

LSM-Trees:

• Leveled compaction: about 1.1x when levels are at their targets (see LSM Level Sizing)
• Compaction needs extra temporary space while old and new files both exist
• Size-tiered compaction needs more space than leveled

Read Amplification

B-Trees:

• Point reads: 2-4 page reads (height of tree)
• Range scans: Minimal additional reads

LSM-Trees:

• Point reads: May check multiple levels (10+ files)
• Bloom filters skip most files that don’t hold the key
• Range scans can be expensive across levels

LSM Level Sizing

Leveled LSM-trees keep a fixed size ratio between neighbouring levels, so the largest level decides almost everything. RocksDB’s default ratio is 10, and with its dynamic level sizing, the default since version 8.4, its docs describe 90% of data sitting in the last level.

Worked example: 6 levels, a largest level of 1 GB, and an assumed size ratio of 10. Interview questions often leave the ratio out, so state it.

These use decimal units and leave out the memtable and L0. For a size ratio T, the total is about largest × T / (T - 1), so the levels above the largest add only about 11% at a ratio of 10.

What this tells you in an interview:

• Space amplification: when the levels are at their targets and the upper levels only hold older versions of keys in the last level, the data on disk is about 1.11x the live data.
• Write amplification: moving data down one level merges each byte with about T bytes from the next level, so the total grows by about T per level.
• Read amplification: a point lookup below L0 checks at most one file per level, and Bloom filters skip most of those checks.
• Changing the ratio: a larger ratio means fewer levels, so reads and space improve, but each level’s compactions rewrite more data.

Real-World Usage

B-Tree Systems

MySQL/InnoDB:

• OLTP workloads
• Strong consistency requirements
• Point lookups and small range scans

PostgreSQL:

• Complex queries with joins
• Mixed workloads with tuning
• ACID compliance critical

LSM-Tree Systems

Cassandra:

• High write throughput
• Time-series data
• Distributed architecture

RocksDB/LevelDB:

• Embedded database engine
• SSD-optimized
• Used by Facebook, LinkedIn

Apache HBase:

• Big data analytics
• Batch processing workloads
• Column-family data model

Optimization Strategies

B-Tree Optimizations

Buffer Pool Management:

-- MySQL InnoDB buffer pool tuning
SET innodb_buffer_pool_size = '70%_of_RAM';
SET innodb_buffer_pool_instances = 8;
SET innodb_old_blocks_time = 1000;

Index Design:

• Clustered index on primary key
• Covering indexes for frequent queries
• Partial indexes for filtered queries

LSM-Tree Optimizations

Compaction Strategies:

• Size-tiered: Compact when level reaches size threshold
• Leveled: Maintain non-overlapping levels
• Hybrid: Combine both strategies

Bloom Filter Tuning:

# Configure Bloom filters to reduce read amplification
bloom_filter_bits_per_key = 10  # 1% false positive rate
block_based_table_options = {
    'filter_policy': rocksdb.BloomFilterPolicy(bloom_filter_bits_per_key),
    'cache_index_and_filter_blocks': True,
}

Write Buffer Management:

# Tune memtable size and count
options = rocksdb.Options()
options.write_buffer_size = 64 * 1024 * 1024  # 64MB
options.max_write_buffer_number = 3
options.min_write_buffer_number_to_merge = 2

Decision Framework

Choose B-Trees When:

• Read-heavy workloads (>80% reads)
• Point lookups are primary access pattern
• Consistent latency required
• OLTP systems with complex queries

Choose LSM-Trees When:

• Write-heavy workloads (>50% writes)
• Sequential/batch writes are common
• High write throughput required
• Time-series data or append-only patterns
• Big data/analytics workloads

Hybrid Approaches

Some modern systems use hybrid approaches:

MySQL X-Engine:

• LSM for writes, B-Tree indexes for reads
• Automatic data migration between structures

TiDB:

• LSM for transaction log (TiKV)
• B-Tree for SQL layer optimization

Understanding the trade-offs between B-Trees and LSM-Trees is crucial for choosing the right storage engine for your workload patterns and performance requirements.