Hello! Welcome to the next lesson in our module on write-optimized storage.
In our previous lessons, we've taken a deep dive into the Log-Structured Merge-Tree (LSM-Tree), analyzing its architecture, compaction strategies, and the fundamental performance trade-offs related to read, write, and space amplification. We established that LSM-Trees are specifically engineered to excel at one thing: ingesting writes at a very high rate.
Today, we'll broaden our perspective. An LSM-Tree isn't the only way to store data on disk; for decades, the dominant structure has been the B+ Tree. This lesson directly addresses the learning outcome: Compare the performance characteristics of LSM-Trees and B+ Trees for write-heavy versus read-heavy workloads.
By the end of this lesson, you'll understand the core design principles of both structures, be able to articulate why each is suited for different tasks, and make informed decisions about which to use based on application requirements. This is a crucial skill, as this choice represents one of the most fundamental trade-offs in database system design.
1. The Fundamental Problem: Disk is Slow
Before we compare the two data structures, let's quickly re-establish the physical reality that dictates their design: the vast performance gap between RAM and persistent storage (SSDs and HDDs).
How Databases Actually Store Your Data (B-Trees vs LSM Trees Explained)
The video 'How Databases Actually Store Your Data' from ByteMonk provides an excellent 90-second primer on why disk I/O is the primary bottleneck that specialized data structures like B-Trees and LSM-Trees are built to overcome.
Watch the segment from 01:03 to 02:35. Pay attention to the orders-of-magnitude difference in access times and the key insight: disks are slow for random access but fast for sequential access.
This is the central challenge: any efficient disk-based data structure must minimize random disk I/O. B+ Trees and LSM-Trees approach this challenge with two very different philosophies.
2. B+ Trees: The Read-Optimized Champion
You've likely encountered B-Trees or B+ Trees in your algorithms and database courses. They are the workhorse behind the indexes in most traditional relational databases like PostgreSQL and MySQL. Their design is a masterclass in optimizing for the "physics of the page."
System Design First Princpal [5/15]: The Physics of Persistence (B-Trees vs LSM-Trees)
To understand why B-Trees are so effective, let's watch a segment from the 'System Design First Principal' series. It gives a great intuition for how a B-Tree's structure is perfectly tuned for disk page access.
Watch from 11:33 to 15:12. Focus on: How a B-Tree's 'fat and shallow' structure minimizes the number of disk reads needed to find any piece of data. The concept of the 'read-modify-write' cycle and why it makes random writes the Achilles' heel of a B-Tree.
As the video explains, the magic of the B+ Tree lies in its structure:
- Optimized for Reads: It's a balanced tree with a very high fanout (hundreds of children per node). This makes the tree extremely shallow. You can find any single record in a database of billions of rows with just 3-4 disk reads—one for each level of the tree. This provides incredibly fast and predictable point lookups. Furthermore, the leaf nodes are linked together in a sorted list, making range scans (e.g.,
WHERE price BETWEEN 100 AND 200) highly efficient. - Pessimized for Writes: The B+ Tree maintains its sorted order by updating data in-place. To insert or update a single record, the database must:
- Read the relevant disk page into memory.
- Modify the page in memory.
- Write the entire page back to its original location on disk.
This "read-modify-write" pattern involves random I/O, which is precisely what disks are bad at. If the page is full, a "page split" may be triggered, causing a cascade of writes that further increases write amplification.
3. LSM-Trees: The Write-Optimized Contender
We've covered the LSM-Tree's internals already, so we'll just recap its performance profile. In stark contrast to the B+ Tree's in-place updates, the LSM-Tree uses an out-of-place, append-only approach.
- Optimized for Writes: All writes go to an in-memory structure (the memtable). When the memtable is full, it's flushed to disk as a new, immutable, sorted file (SSTable). This write is a single, large, sequential operation—the fastest way to write to disk. This design allows LSM-Trees to achieve exceptionally high write throughput.
- Pessimized for Reads: The trade-off is that a single record could be in the memtable or in any of the numerous SSTables on disk. A point lookup might require checking many places. This increases read amplification. As we've learned, this is mitigated by using Bloom filters to quickly rule out SSTables and by a background compaction process that merges SSTables to reduce their number. However, a read is fundamentally more complex than a B+ Tree's simple tree traversal.
4. Head-to-Head: A Direct Comparison
Now that we have a clear picture of both designs, let's put them side-by-side.
LSM Tree vs. B+ Tree - Ken Wagatsuma's Homepage
The blog post 'LSM Tree vs. B+ Tree' by Ken Wagatsuma provides a wonderfully concise summary table and a practical checklist for choosing between them. We'll use this as our guide.
First, study the comparison table at the top of the article. Then, read the checklist under the heading 'When to Choose LSM-Tree Over B+ Tree?'. This provides a clear, practical summary of the key trade-offs.
Let's use the insights from that reading to analyze a performance graph.
This graph perfectly illustrates the core performance trade-off:
- B+ Trees offer low, predictable latency for reads at the cost of higher latency for writes.
- LSM-Trees offer very low latency for writes at the cost of higher and more variable latency for reads.
Test your understanding!
You are designing a system to store user activity events for an analytics platform. The system will receive millions of events per second from websites and mobile apps. The primary query pattern is running large analytical queries over week-long or month-long ranges of data, typically during off-peak hours. Storage cost is also a concern.
Which data structure, B+ Tree or LSM-Tree, would be a better fit, and why? Justify your choice based on at least two of the following: write performance, read performance, or storage efficiency/compression.
Show answer
An LSM-Tree would be the far better choice for this system.
Justification:
- Write Performance: The workload is extremely write-heavy ("millions of events per second"). LSM-Trees are optimized for high-throughput ingestion because they turn all writes into fast, sequential I/O, avoiding the random I/O bottlenecks that a B+ Tree would face under this load.
- Read Performance: The read workload consists of large range scans, not low-latency point lookups. LSM-Trees perform well on range scans because data within each SSTable is sorted. While reads might be slower than a B+ Tree, the workload is not sensitive to millisecond-level read latency, making the LSM-Tree's read performance acceptable.
- Storage Efficiency: The blog post mentions that LSM-Trees can achieve higher compression and better storage utilization. Because SSTables are immutable, they are very amenable to aggressive compression. This is a significant advantage when storing massive amounts of historical event data.
5. A Deeper Look: Concurrency and Real-World Performance
The simple story is "B+ Trees for reads, LSM-Trees for writes." But the reality, especially in highly concurrent systems, has more nuance.
Let's look at a benchmark comparing RocksDB (a popular LSM-Tree implementation) and a B+ Tree.
- For reads (a, b), the B+-tree is highly competitive, as expected.
- For writes (c), notice something interesting. At a low thread count (1), the B+-tree performs well. But as concurrency increases (16 threads), the LSM-Tree implementations (RocksDB, WiredTiger) pull ahead.
Why is this? A B+ Tree's in-place updates require taking locks on pages of the tree to prevent race conditions. Under high concurrent write load, different threads will constantly be competing for locks on the same set of "hot" pages (especially those near the right edge of the tree for sequential key inserts), creating a bottleneck.
LSM-Trees, with their append-only write path, largely sidestep this issue. Writes are isolated from each other until the compaction phase, allowing for much higher write concurrency. This is a critical engineering detail that makes LSM-Trees so successful in modern, large-scale, write-heavy systems.
Conclusion
We've now compared the two titans of disk-based data structures. Your choice as an engineer depends entirely on understanding your application's access patterns.
Key Takeaways:
- B+ Trees optimize for reads. Their shallow, sorted, in-place structure is designed to minimize random I/O for lookups, making them ideal for read-heavy transactional (OLTP) workloads where low-latency point and range queries are critical.
- LSM-Trees optimize for writes. Their append-only, out-of-place design leverages fast sequential I/O, making them perfect for write-heavy workloads like logging, metrics, and event streaming.
- This is a classic engineering trade-off. B+ Trees trade slower random writes for fast reads. LSM-Trees trade more complex, potentially slower reads for extremely fast writes.
- In highly concurrent systems, LSM-Trees often have a significant advantage for writes due to less lock contention compared to B+ Trees.
Preview of the Next Lesson
We've discussed B+ Trees at a high level, focusing on their performance profile. In the next module, we will begin a deep dive into their implementation. Our first lesson will answer a fundamental question: "Why are B+ trees preferred over binary search trees for disk-based indexing?" We'll explore why the "fat and shallow" design is not just a good idea, but an absolute necessity when working with block-based storage like a disk.