0% completed
Storage Engines: B-Trees vs LSM-Trees
On This Page
Part 1: Three Costs Every Engine Pays
Part 2: How a B-Tree Writes
Part 3: How an LSM Tree Writes
Part 4: How an LSM Tree Reads
Part 5: Compaction Chooses Which Cost to Pay
Part 6: Matching the Engine to the Workload
Part 7: Using This in an Interview
Common Mistakes
Key Takeaways
When an application writes one byte to a database, how many bytes reach the disk? Take a fitness company that stores heart-rate readings from 2 million watches in Postgres. For this company, the answer is about three. The application writes about 10 MB of row data each second, and the disk records about 30 MB.
The other 20 MB come from the database itself, and nothing is misconfigured. These numbers are made-up examples. Every storage engine writes extra bytes, and the two main designs differ in where those extra bytes come from. This lesson compares the two designs on three costs, and then shows which workload each one suits.
Part 1: Three Costs Every Engine Pays
A storage engine is the part of a database that lays data out on disk and finds it again. There are two main families of engines:
- Postgres and MySQL use B-trees to find rows.
- RocksDB and Cassandra use LSM trees.
Neither family is faster in general. Each one moves work between three costs, and each cost is a ratio called an amplification:
- Write amplification compares the bytes written to the storage device with the bytes the application wrote. In the opening example, it is 30 divided by 10, or three.
- Read amplification counts the separate places, pages or files, that the engine must check to answer one lookup.
- Space amplification compares the bytes held on disk with the bytes of live data. Live data is the current version of each row.
Only write amplification compares two byte rates.
The fitness company has two kinds of data. Heart-rate readings arrive constantly and are read by time range. Profiles and subscriptions are read often and updated in place. Part 6 matches each kind to an engine.
Part 2: How a B-Tree Writes
Postgres stores the company's data today, so B-trees come first. A B-tree is a sorted tree of pages. A page is a fixed-size block of storage, often 8 or 16 KB. The tree has two kinds of pages at its ends:
- The root is the top page. It points to child pages.
- The leaves are the bottom pages. They hold the keys in sorted order.
A lookup reads one page at each level, from the root down to a leaf. Even a billion rows need only about four levels, and the upper levels are usually in memory. For this reason, read amplification is low and steady.
An update takes three steps.
Step 1: Write to the log. The change is first appended to a write-ahead log. This file records every change before the data files are updated, so the database can recover after a crash.
Step 2: Change the page in place. The leaf page that holds the row is changed in memory.
Step 3: Write the page later. The whole page goes to disk in the background, even if only 100 bytes changed.
An update fits into its page, but an insert into a full leaf page does not. The page needs a split. The diagram below shows one.
The entries of the full page are divided between two pages. The parent page gains a pointer to the new page and a separator key. A separator key is the boundary value that tells a lookup which page to read. After the split, each page is about half full, so a B-tree also uses some extra space.
Notice the line at the bottom of the diagram: one insert caused four writes. One logical write became several physical writes: a log record, the old leaf, the new leaf, and the parent. Splits and whole-page writes are where a B-tree's write amplification comes from. They are also random writes, which land at scattered places on the disk.
Part 3: How an LSM Tree Writes
A B-tree changes pages where they are. An LSM tree takes the opposite approach. LSM stands for log-structured merge. An LSM tree never changes data in place. It collects writes in memory and writes them out in large sorted files.
Step 1: Write to the log. As with a B-tree, the change goes to a log first.
Step 2: Add it to the memtable. A memtable is a sorted structure in memory that holds recent writes.
Step 3: Flush to a file. A full memtable is written to disk as one sorted file, called an SSTable. An SSTable is never changed after it is written.
Because files never change, an update cannot overwrite the old value. It writes a new version of the key into a newer file. A delete writes a tombstone, which is a marker that says the key was deleted. For this reason, old versions stay on disk for a while.
Step 4: Compact in the background. Compaction merges files in the background. It keeps the newest version of each key and drops old versions and tombstones.
The first write is cheap and sequential, which means it goes to one continuous region of the disk. But compaction rewrites the same data several times. For the same 10 MB a second of readings, a common LSM setup might send about 100 MB a second to the device, against the B-tree's 30.
That larger number is often easier for the device. A solid-state drive absorbs long sequential writes with much less internal work than small random ones. Therefore, the pattern of the writes can matter more than their total.
Part 4: How an LSM Tree Reads
The cheap writes of Part 3 have a cost at read time, because one key can now be stored in several places. The engine checks the memtable first, then the files from newest to oldest. The first version it finds is the current one, and every file it opens adds to read amplification.
To skip most files, each SSTable keeps a Bloom filter, a small summary of the keys in that file. For one key, the filter answers "definitely not here" or "maybe here." The diagram below shows a lookup that uses these filters.
Notice that File 3 was skipped without being opened, while File 2 was opened because of a false positive and did not hold the key.
A Bloom filter can be wrong in one direction only. It can say "maybe" for a key that is not in the file, which is called a false positive. It never says "no" for a key that is in the file. For this reason, a "no" is certain, and the engine skips that file without opening it. A "maybe" still has to be checked.
A standard Bloom filter does not help a range scan, such as one watch's last hour of readings. The filter answers questions about one key, and a range covers many keys. That scan must therefore merge every file that covers the range.
Part 5: Compaction Chooses Which Cost to Pay
Parts 3 and 4 showed that compaction adds writes, and that many files make reads slower. How compaction merges files decides the balance between the three costs. There are two common methods.
Size-tiered compaction merges several files of similar size into one larger file. Each byte is rewritten only a few times. But many files can hold the same key, so reads check more files. Old versions also stay on disk until the next merge, which uses more space.
Leveled compaction arranges files in levels, and each level is about ten times larger than the one above it. Inside each level below the first, no two files cover the same keys. A lookup therefore checks about one file per level, and old versions are removed sooner. But each byte is rewritten many times as it moves down the levels.
The diagram below compares the B-tree and the two methods on the three costs.
Notice that no design is low on all three costs. Moving from size-tiered to leveled compaction lowers read and space amplification, and it raises write amplification substantially.
Compaction has one more cost. It uses CPU and disk, so it competes with reads. Reads can slow down during heavy compaction.
Part 6: Matching the Engine to the Workload
Part 1 described the company's two kinds of data. With the three costs in mind, each one favors a different engine.
| Workload | Usually favors | Why |
|---|---|---|
| Heart-rate readings: constant inserts, rarely updated, read in time ranges | An LSM tree | Sequential writes keep up with heavy ingest |
| Profiles and subscriptions: frequent reads, updates in place, transactions | A B-tree | One short path per lookup gives steady read times |
Do not switch too early, though. At 10 MB a second, a B-tree on a good disk may keep up. Move the readings when measured device writes are the actual limit, not when growth is only expected. To check, compare the device's write rate with the application's, and with what the disk can sustain. When Postgres Stops Being Enough, later in this chapter, covers the cost of adding a second store.
Part 7: Using This in an Interview
Storage engines usually come up in the deep dive, when one part of your design is examined in detail. The interviewer asks why you chose a database.
"The readings are about 10 MB a second of inserts, read by time range. That suits an LSM store, because its writes are sequential. The cost is compaction, which competes with reads. Profiles stay in Postgres, where reads are short and predictable. I would move the readings only if measured disk writes became the limit."
Expect two follow-up questions. "What happens to read latency during compaction?" Compaction competes for the disk, and you can limit its speed. "Why not leveled compaction everywhere?" It gives cheaper reads and less space, but it costs many more rewritten bytes.
Common Mistakes
Mistake 1: Saying an LSM tree is faster without naming the cost. Its first writes are cheap, but compaction, read amplification, and extra space pay for them.
Mistake 2: Comparing only the bytes written. Sequential writes at a higher rate can be easier for a drive than random writes at a lower rate.
Mistake 3: Choosing an engine from an expected future. Change engines when a measured number shows the current one is the limit, because a second store has its own costs.
Key Takeaways
- Every engine pays three costs. Write amplification compares bytes, read amplification counts places checked, and space amplification compares disk with live data.
- A B-tree changes pages in place. Reads are short and steady, and a full page splits, which adds writes to the parent.
- An LSM tree appends and merges later. First writes are cheap and sequential, and compaction rewrites the data several times.
- A Bloom filter's "no" is certain. It lets a lookup skip a file, while a "maybe" must still be checked.
- In a system design interview, name the workload, then the engine, then the cost you accept and the measurement that would change your choice.
The next lesson, MVCC and Isolation Levels in Practice, explains how a database lets many transactions read and write the same rows at once.
Reading Progress
0%
On This Page
Part 1: Three Costs Every Engine Pays
Part 2: How a B-Tree Writes
Part 3: How an LSM Tree Writes
Part 4: How an LSM Tree Reads
Part 5: Compaction Chooses Which Cost to Pay
Part 6: Matching the Engine to the Workload
Part 7: Using This in an Interview
Common Mistakes
Key Takeaways