B-Tree vs LSM-Tree: Deep Dive into Database Storage Engines

When you query a database, the storage engine silently works behind the scenes to fetch or write data efficiently. Two dominant data structures power most modern databases: B-Trees and LSM-Trees. Understanding their internals is crucial for optimizing performance, diagnosing production issues, and designing scalable systems. B-Trees, used by MySQL InnoDB and PostgreSQL, offer balanced read performance with predictable latency. LSM-Trees, powering Cassandra, RocksDB, and LevelDB, prioritize write throughput by batching writes and deferring organization. This article dissects both structures, compares their trade-offs, and provides practical debugging guides. You'll learn how to choose the right engine for your workload, diagnose common pitfalls, and avoid production incidents.

B-Tree Internals: Structure and Operations

A B-Tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time. It is optimized for systems that read and write large blocks of data. The tree consists of nodes: internal nodes contain keys and pointers to child nodes, while leaf nodes contain actual data or pointers to data. The height of the tree is kept low by having a high branching factor (often hundreds of children per node). This minimizes disk I/O because each node corresponds to a disk page. Insertions and deletions may cause node splits or merges to maintain balance. B-Trees are the default storage engine for many relational databases (e.g., InnoDB, PostgreSQL). They excel at point queries and range scans due to their sorted structure. However, they suffer from write amplification because updates often require rewriting entire pages.

-- Example: Creating a B-Tree index in MySQL (InnoDB)
CREATE TABLE employees (
    id INT PRIMARY KEY,
    name VARCHAR(100),
    department VARCHAR(50),
    salary DECIMAL(10,2),
    INDEX idx_department (department)
) ENGINE=InnoDB;

-- Insert some data
INSERT INTO employees VALUES
(1, 'Alice', 'Engineering', 90000),
(2, 'Bob', 'Marketing', 80000),
(3, 'Charlie', 'Engineering', 95000);

-- Query using the index
EXPLAIN SELECT * FROM employees WHERE department = 'Engineering';

LSM-Tree Internals: Structure and Operations

An LSM-Tree (Log-Structured Merge-Tree) is designed for high write throughput by converting random writes into sequential writes. Data is first written to an in-memory memtable (often a sorted structure like a red-black tree). When the memtable reaches a threshold, it is flushed to disk as an immutable SSTable (Sorted String Table). Over time, multiple SSTables accumulate, and a background compaction process merges them to maintain order and reclaim space. Reads must check the memtable and all SSTables, so bloom filters are used to quickly skip irrelevant SSTables. LSM-Trees are used in NoSQL databases like Cassandra, HBase, and key-value stores like RocksDB and LevelDB. They excel in write-heavy workloads but can suffer from read amplification and compaction overhead. Write amplification is a key concern: each write may be rewritten multiple times during compaction.

-- Example: Creating a table in Cassandra (LSM-Tree based)
CREATE TABLE sensor_data (
    sensor_id UUID,
    timestamp TIMESTAMP,
    value DOUBLE,
    PRIMARY KEY (sensor_id, timestamp)
) WITH compaction = { 'class': 'LeveledCompactionStrategy' };

-- Insert some data
INSERT INTO sensor_data (sensor_id, timestamp, value) VALUES
(uuid(), '2023-01-01 00:00:00', 23.5),
(uuid(), '2023-01-01 00:01:00', 24.0);

-- Query using partition key
SELECT * FROM sensor_data WHERE sensor_id = ?;

Read and Write Amplification: The Hidden Cost

Amplification factors measure the extra I/O caused by the storage engine. Write amplification (WA) is the ratio of bytes written to disk to bytes written by the application. B-Trees have moderate WA due to page splits and writes, while LSM-Trees can have high WA during compaction. Read amplification (RA) is the number of disk reads per query. B-Trees have low RA for point queries (one or two page reads), but LSM-Trees may need to check multiple SSTables. Bloom filters reduce RA by eliminating unnecessary SSTable reads. Space amplification (SA) is the ratio of disk space used to logical data size. LSM-Trees can have high SA if compaction lags, leaving obsolete data. Understanding these trade-offs helps in selecting the right engine and tuning parameters. For example, in a write-heavy logging system, LSM-Tree with leveled compaction may be optimal, while a user profile database with frequent reads benefits from B-Tree.

-- Check write amplification in MySQL (InnoDB)
SHOW GLOBAL STATUS LIKE 'Innodb_data_written';

-- Check disk space usage
SELECT table_schema, SUM(data_length + index_length) / 1024 / 1024 AS size_mb
FROM information_schema.tables
GROUP BY table_schema;

-- For Cassandra, check compaction metrics
SELECT * FROM system.compaction_history;

Choosing Between B-Tree and LSM-Tree

The choice depends on your workload. B-Trees are ideal for OLTP applications with many point queries, small range scans, and moderate write rates. They provide strong consistency and predictable performance. LSM-Trees excel in write-heavy scenarios like time-series data, logging, and event sourcing. They offer higher write throughput and efficient compression. However, they may have higher read latency for point queries due to multiple SSTable lookups. Consider also the operational complexity: B-Trees require careful tuning of buffer pool size, while LSM-Trees need compaction tuning. Hybrid approaches exist, such as using a B-Tree for hot data and LSM-Tree for cold data. Many modern databases offer configurable storage engines (e.g., MySQL with MyRocks). Evaluate your access patterns: if writes dominate, LSM-Tree is likely better; if reads dominate, B-Tree is safer.

-- Analyze read/write ratio from MySQL performance_schema
SELECT
    (SUM(COUNT_READ) / (SUM(COUNT_READ) + SUM(COUNT_WRITE))) * 100 AS read_pct,
    (SUM(COUNT_WRITE) / (SUM(COUNT_READ) + SUM(COUNT_WRITE))) * 100 AS write_pct
FROM performance_schema.table_io_waits_summary_by_table
WHERE object_schema = 'mydb';

Concurrency and Crash Recovery

B-Trees use techniques like latch-free B-Trees or page-level locking to handle concurrent access. InnoDB uses a combination of row-level locks and MVCC (Multi-Version Concurrency Control) to allow concurrent reads and writes. Crash recovery is handled via a write-ahead log (WAL) that records changes before they are applied to pages. LSM-Trees also use WAL for durability. Compaction can be concurrent, but careful scheduling is needed to avoid conflicts. LSM-Trees typically have simpler concurrency because SSTables are immutable; reads and writes don't conflict. However, compaction may interfere with reads. Both engines rely on checkpoints to limit recovery time. Understanding these mechanisms is vital for tuning performance and ensuring data integrity.

-- Check InnoDB recovery status
SHOW ENGINE INNODB STATUS\G

-- Look for 'LOG' section for recovery progress
-- Example output snippet:
-- Log sequence number 123456789
-- Log flushed up to   123456789
-- Last checkpoint at  123456000

Performance Tuning and Best Practices

For B-Trees, key tuning parameters include buffer pool size, page size, and index fill factor. A larger buffer pool reduces disk reads. Page size affects node fan-out: larger pages reduce tree height but increase write amplification. For LSM-Trees, tune memtable size, compaction strategy, and bloom filter false positive rate. Leveled compaction reduces read amplification at the cost of higher write amplification. Use compression to reduce disk space and I/O. Monitor compaction throughput and adjust number of compaction threads. Both engines benefit from SSD storage due to lower latency. Regularly rebuild indexes to reduce fragmentation. Use database-specific tools like MySQL's pt-online-schema-change for zero-downtime schema changes. For LSM-Trees, schedule compaction during off-peak hours.

-- InnoDB tuning example
SET GLOBAL innodb_buffer_pool_size = 8 * 1024 * 1024 * 1024; -- 8GB
SET GLOBAL innodb_log_file_size = 2 * 1024 * 1024 * 1024; -- 2GB

-- Cassandra tuning (cqlsh)
ALTER TABLE sensor_data WITH compaction = {'class': 'LeveledCompactionStrategy', 'sstable_size_in_mb': 160};

-- Check current settings
SHOW VARIABLES LIKE 'innodb_buffer_pool_size';