As a rule of thumb, LSM-trees are better suited for write-heavy applications, whereas B-trees are faster for reads. However, benchmarks are often sensitive to details of the workload. You need to test systems with your particular workload to make a valid comparison. Moreover, it’s not a strict either/or choice between LSM- and B-trees; storage engines sometimes blend characteristics of both approaches—for example, by having multiple B-trees and merging them LSM-style. In this section, we will briefly discuss a few things that are worth considering when measuring the performance of a storage engine.
Read performance
In a B-tree, looking up a key involves reading one page at each level. Since the number of levels is usually quite small, reads from a B-tree are generally fast and have predictable performance. In an LSM storage engine, reads often have to check several SSTables at different stages of compaction, but Bloom filters help reduce the number of disk I/O operations required. Both approaches can perform well, and which is faster depends on the details of the storage engine and the workload.
Range queries are simple and fast on B-trees, as they can make use of the sorted structure of the tree. On LSM storage, range queries can also take advantage of the SSTable sorting, but they need to scan all the segments in parallel and combine the results. Bloom filters don’t help for range queries (since you would need to compute the hash of every possible key within the range, which is impractical), making range queries more expensive than point queries in the LSM approach.
High write throughput can cause latency spikes in a log-structured storage engine if the memtable fills up. This happens if data can’t be written out to disk fast enough, perhaps because the compaction process cannot keep up with incoming writes. Many storage engines, including RocksDB, apply backpressure in this situation: they suspend all reads and writes until the memtable has been written out to disk.
Regarding read throughput, modern SSDs (especially NVMe [Non-Volatile Memory Express] SSDs that connect through the much faster PCIe bus rather than the SATA bus) can perform many independent read requests in parallel. Both LSM-trees and B-trees are able to provide high read throughput, but storage engines need to be carefully designed to take advantage of this parallelism.
Sequential versus random writes
With a B-tree, if the application writes keys that are scattered all over the key space, the resulting disk operations are also scattered randomly, since the pages that the storage engine needs to overwrite could be located anywhere on disk. On the other hand, a log-structured storage engine writes entire segment files at a time (either writing out the memtable or while compacting existing segments), which are much bigger than a page in a B-tree.
The pattern of many small, scattered writes (as found in B-trees) is called random writes, while the pattern of fewer large writes (as found in LSM-trees) is called sequential writes. Disks generally have higher sequential write throughput than random write throughput, which means that a log-structured storage engine can generally handle higher write throughput on the same hardware than a B-tree. This difference is particularly big on spinning-disk hard drives; on the SSDs that most databases use today, the difference is smaller but still noticeable.
Sequential Versus Random Writes on SSDs
On spinning-disk hard drives (HDDs), sequential writes are much faster than random writes. This is because a random write has to mechanically move the disk head to a new position and wait for the right part of the platter to pass underneath the disk head, which takes several milliseconds—an eternity in computing timescales. However, SSDs including NVMe (or flash memory attached to the PCI Express bus) have now overtaken HDDs for many use cases, and they are not subject to such mechanical limitations.
Nevertheless, SSDs also have higher throughput for sequential writes than for random writes. The reason is that flash memory can be read or written one page (typically 4 KiB) at a time, but it can be erased only one block (typically 512 KiB) at a time. Some pages in a block may contain valid data, whereas others may contain data that is no longer needed. Before erasing a block, the controller must move pages containing valid data into other blocks; this process is called garbage collection (GC).
A sequential write workload writes larger chunks of data at a time, so it is likely that a whole 512 KiB block belongs to a single file. When that file is later deleted again, the whole block can be erased without having to perform any GC. On the other hand, with a random write workload, a block more likely contains a mixture of pages with valid and invalid data, so the garbage collector has to perform more work before a block can be erased. The write bandwidth consumed by GC is then not available for the application. The additional writes performed because of GC also contribute to wear on the flash memory; therefore, random writes wear out the drive faster than sequential writes.
Write amplification
With any type of storage engine, one write request from the application turns into multiple I/O operations on the underlying disk. With LSM-trees, a value is first written to the log for durability, then again when the memtable is written to disk, and again every time the key-value pair is part of a compaction. (If the values are significantly larger than the keys, this overhead can be reduced by storing values separately from keys and performing compaction only on SSTables containing keys and references to values.)
A B-tree index must write every piece of data at least twice: once to the write-ahead log, and once to the tree page itself. In addition, writing out an entire page is sometimes necessary, even if only a few bytes in that page changed, to ensure that the B-tree can be correctly recovered after a crash or power failure.
If you take the total number of bytes written to disk in a workload and divide that by the number of bytes you would have to write if you simply wrote an append-only log with no index, you get the write amplification. (Sometimes write amplification is defined in terms of I/O operations rather than bytes.) In write-heavy applications, the bottleneck might be the rate at which the database can write to disk. In this case, the higher the write amplification, the fewer writes per second it can handle within the available disk bandwidth.
Write amplification is a problem in both LSM-trees and B-trees. Which one is better depends on various factors, such as the length of your keys and values and how often you overwrite existing keys versus insert new ones. For typical workloads, LSM-trees tend to have lower write amplification because they don’t have to write entire pages and they can compress chunks of the SSTable. This is another factor that makes LSM storage engines well suited for write-heavy workloads.
Besides affecting throughput, write amplification is also relevant for the wear on SSDs. A storage engine with lower write amplification will wear out the SSD less quickly.
When measuring the write throughput of a storage engine, it is important to run the experiment for long enough that the effects of write amplification become clear. When writing to an empty LSM-tree, no compactions are going on yet, so all the disk bandwidth is available for new writes. As the database grows, new writes need to share the disk bandwidth with compaction.
Disk space usage
B-trees can become fragmented over time; for example, if a large number of keys are deleted, the database file may contain a lot of pages that are no longer used by the B-tree. Subsequent additions to the B-tree can use those free pages, but they can’t easily be returned to the operating system because they are in the middle of the file, so they still take up space on the filesystem. Databases therefore need a background process that moves pages around to place them better, such as the vacuum process in PostgreSQL.
Fragmentation is less of a problem in LSM-trees, since the compaction process periodically rewrites the data files anyway, and SSTables don’t have pages with unused space. Moreover, blocks of key-value pairs can better be compressed in SSTables, often resulting in smaller files on disk than with B-trees. Keys and values that have been overwritten continue to consume space until they are removed by a compaction, but this overhead is quite low when using leveled compaction. Size-tiered compaction (see “Compaction strategies”) uses more disk space, especially temporarily during compaction.
Having multiple copies of some data on disk can also be a problem when you need to delete some data and be confident that it really has been deleted (perhaps to comply with data protection regulations). For example, in most LSM storage engines a deleted record may still exist in the higher levels until the tombstone representing the deletion has been propagated through all the compaction levels, which might take a long time. Specialist storage engine designs can propagate deletions faster.
On the other hand, the immutable nature of SSTable segment files is useful if you want to take a snapshot of a database at some point in time (e.g., for a backup or to create a copy of the database for testing). You can write out the memtable and record which segment files existed at that time. As long as you don’t delete the files that are part of the snapshot, you don’t need to actually copy them. In a B-tree whose pages are overwritten, taking such a snapshot efficiently is more difficult.