CS Fundamentals Trainer · Guides
Storage engines: B-trees and LSM trees
How B-trees update pages in place and LSM trees append, flush and compact, with measured write, read and space amplification, Bloom filters, compaction strategies and when to choose which.
32 min read
Every database has to answer two questions: how do I find a row quickly? and how do I change the data on disk without losing it? The two classic answers are the B-tree, which keeps the data sorted in fixed-size pages that it updates in place, and the log-structured merge tree (LSM tree), which never updates in place: it appends to a log and sorts and merges in the background. Postgres, MySQL's InnoDB, SQLite and most relational databases use B-trees; RocksDB, LevelDB, Cassandra, HBase and ScyllaDB use LSM trees. Neither is better. They trade write amplification, read amplification and space amplification against each other, and understanding that trade is how you choose between them and tune either.
This guide builds both from scratch. I measured SQLite (a real B-tree) and wrote small simulations of a B+tree and an LSM tree, so every number below can be reproduced from the appendix. It builds on database indexes, on the memory hierarchy, and on the page and caching ideas in operating systems.
Three kinds of evidence, kept apart. Numbers in this guide come from three different sources, and they should not be mixed up: | Label | What it is | How far to trust it | |---|---|---| | Real SQLite | measured on SQLite, a production B-tree engine, on this virtual machine | real behaviour, but one engine, one machine and a small data set | | Toy B+tree / toy LSM | my Python models that count pages and entries; they store no data and have no disk, no locks and no CPU cost | the direction and rough size of an effect (for example "tiered compaction writes less"); never the speed of any real database | | Documentation | what the engines' manuals and papers say; not run here | as good as the source | Every experiment heading below says which it is. The toy has no real LSM engine to compare with, because RocksDB and similar libraries could not be installed in the sandbox, so no measurement here compares a real B-tree with a real LSM tree. Section 4.1 shows how much the answer moves with the settings and the workload.
1. The constraint: disks like big, sequential I/O
Storage is read and written in blocks (4 KB or more), and a block costs the same whether you want 1 byte or all 4,096. Flash and disks also prefer sequential access to random access. On this virtual machine (a real measurement, not a model), writing 4 KB blocks one after another with a flush every 64 writes ran at about 207 MB/s, and the same writes to random places in a 1 GB file at about 92 MB/s, a bit over twice as slow. On a spinning disk the gap is two orders of magnitude, and on SSDs random writes also wear the device faster, because flash must erase a large block to rewrite one page. A storage engine is largely a strategy for turning the application's small, random writes into something the device likes.
Three numbers describe any engine:
- Write amplification: bytes physically written per byte the application wrote.
- Read amplification: how many disk reads (or pages, or tables) one lookup needs.
- Space amplification: bytes on disk per byte of live data.
You cannot minimise all three at once (the "RUM conjecture": reads, updates, memory). Each design picks a corner.
2. The B-tree
A B-tree (in databases, almost always a B+tree) stores sorted keys in pages. Interior pages hold keys and pointers to child pages; the leaf pages hold the records (or pointers to them), and are linked to their neighbours so range scans can walk along the leaves.
Diagram: A B+tree: few levels, wide pages
Because a page holds hundreds of keys, the tree is very shallow. With a 4 KB page and 16 bytes per key-and-pointer entry, an interior page has a fan-out of about 250; three levels of interior pages index about 250 × 250 × 250 ≈ 15 million leaf pages, and four levels reach billions of rows. A lookup in a table of a billion rows reads about four pages, and the top levels stay in the buffer pool, so in practice it is one disk read. That is the B-tree's great strength: predictable, low read amplification.
Updates happen in place
To insert, find the leaf and add the record. If the leaf is full it splits into two half-full pages and the parent gets a new key (which can split in turn, up to the root). To make this crash-safe, the engine first appends the change to a write-ahead log (WAL), and writes the modified pages back later; after a crash it replays the log. So every change is written twice: once to the log, once to the page.
Experiment 1 (toy B+tree): fill factor and key order
I built a B+tree with 40 records per leaf and inserted 100,000 keys, once in increasing order and once in random order:
| Insert order | Leaf pages | Average fill | Splits |
|---|---|---|---|
| sequential keys | 2,500 | 100% | 2,499 |
| random keys | 3,574 | 70% | 3,573 |
Appending at the right edge keeps every page full (the split leaves the old page full and starts a new one). Random inserts split pages in half again and again, and settle at about 70% full (the theoretical average is ln 2 ≈ 69%). Random keys therefore use about 43% more pages for the same data, which is more space on disk and less data per cache line of the buffer pool. This is the practical reason to be careful with random identifiers as clustered primary keys: a random UUID inserts everywhere, while a time-ordered id inserts at the end. (SQLite is smarter about the sequential case than my toy; in a test of 300,000 rows its file was about the same size for both orders, but it inserted the sequential keys at 659,000 rows per second against 183,000 for random ones, 3.6 times faster, because random inserts touch a different page every time and the 2 MB page cache I gave it could not hold them.)
Experiment 2 (toy B+tree): write amplification of in-place updates
A change of a 100-byte record must rewrite the whole 4 KB page. I took a tree of 100,000 records and inserted 20,000 more random ones, writing back every modified page after every n inserts:
| Write-back after every | Page writes per record | Bytes written per byte of data |
|---|---|---|
| 1 insert | 1.00 | 41.0 |
| 10 inserts | 1.00 | 40.9 |
| 100 inserts | 0.99 | 40.6 |
| 1,000 inserts | 0.93 | 38.0 |
| 10,000 inserts | 0.56 | 22.8 |
For small random writes, a B-tree writes about 40 times more bytes than the application asked for (and the WAL adds more). Only when thousands of inserts share a page between write-backs (large batches, or a buffer pool that absorbs many changes before a checkpoint) does the cost fall. Real engines reduce it with big buffer pools and group commit, but the fundamental fact stays: an in-place update costs a page.
Other B-tree costs
- Fragmentation: deletes and splits leave partly empty pages. Engines reclaim them with vacuuming,
OPTIMIZEor reindexing. - Concurrency: pages are shared between readers and writers, so engines use latches and multi-version concurrency control (the isolation levels guide covers how Postgres keeps old row versions).
- Torn pages: a crash in the middle of a page write can leave half of the page. Postgres writes whole pages to its WAL the first time a page changes after a checkpoint ("full-page writes") to be able to repair it, which is another source of write amplification.
3. The LSM tree
An LSM tree turns the problem round: never modify anything on disk. Writes are cheap because they only go to memory (and a sequential log); sorting, deduplication and cleanup are paid for later, in batches.
Diagram: The write path and read path of an LSM tree
- A write is appended to a log (for durability) and inserted into an in-memory sorted structure, the memtable.
- When the memtable is full, it is written to disk in one sequential pass as an immutable sorted table, an SSTable (sorted string table), and a new memtable starts.
- Tables accumulate. A read must check the memtable and then the tables, newest first, because a newer version of a key hides older ones.
- In the background, compaction merges tables: it combines several sorted tables into one, keeps only the newest version of each key, and drops deleted keys. A delete is recorded as a tombstone, a marker that hides older values until compaction removes both.
Step through a small example. It has a memtable of four entries, merges level 0 into level 1 when two tables exist, and ends with a lookup of a key that was never written. Switch on the Bloom filter option to compare the read cost:
Interactive animation: lsm tree
In this run, 12 writes cost 19 entries written to disk: 12 into flushed tables plus 7 rewritten by the compaction (write amplification 1.6 so far; it grows as the data goes through more levels). And the lookup of the missing key needed 2 table reads without filters and none with them.
Read amplification and Bloom filters
A lookup might have to look in every table, which is the weakness of the LSM tree. Two tools fix most of it:
- A Bloom filter per table: a compact bit array that answers "definitely not in this table" or "maybe". A filter with 10 bits per key has about a 1% false positive rate, so a lookup for a key skips almost all tables that do not hold it.
- Sorted, non-overlapping tables per level, so that within a level only one table can hold the key (this is what leveled compaction guarantees).
Experiment 3 (toy LSM tree): the compaction trade-off
I wrote a small LSM tree with a memtable of 200 entries and sent it 300,000 random writes to 100,000 distinct keys, so each key was overwritten about three times. I compared leveled compaction (each level is one sorted run, a factor T bigger than the one above; data is rewritten each time it moves down) with size-tiered compaction (when T tables of similar size exist, merge them into one bigger table), with and without Bloom filters (10 bits per key):
| Strategy | Tables | Write amplification | Space | Table reads per lookup, key present (no filter / filter) | Table reads, key absent (no filter / filter) |
|---|---|---|---|---|---|
| leveled, T = 10 | 4 | 12.8 | 1.63x | 3.1 / 1.0 | 4.00 / 0.03 |
| leveled, T = 4 | 6 | 9.1 | 1.48x | 5.2 / 1.0 | 6.00 / 0.05 |
| size-tiered, T = 4 | 10 | 4.9 | 1.77x | 8.1 / 1.1 | 10.00 / 0.08 |
| size-tiered, T = 10 | 22 | 3.1 | 1.88x | 18.3 / 1.1 | 22.00 / 0.19 |
Read it from left to right:
- Tiered compaction writes less (3.1 to 4.9 times against 9 to 13), because each entry is rewritten once per tier and not repeatedly into the next level, but leaves more tables to search and more stale versions on disk (space 1.77 to 1.88 times the live data).
- Leveled compaction reads less and wastes less space, and costs more writing, because merging a level into the next rewrites the data that was already there. A bigger size ratio T means fewer levels but more rewriting per level.
- Bloom filters change the read side completely: the number of table reads for an absent key fell from 4 to 22 down to 0.03 to 0.19, and a present key needed about one read. With filters, the extra tables of the tiered strategy cost memory (the filters) and not disk reads.
(The space figures are a snapshot at the end of the run and depend on when the last compaction happened; the shape is what matters. Real engines, such as RocksDB, compact individual files in the background instead of whole levels, so their numbers are smoother.) Compare the 3 to 13 bytes written per byte in the toy LSM tree with the 40 of the toy B-tree: an LSM tree turns many small random writes into a few large sequential ones, which is why it suits write-heavy workloads such as logs, time series, messaging and ingest pipelines.
The costs of an LSM tree
- Compaction is a hidden workload. It uses disk bandwidth and CPU in the background, and when writes arrive faster than compaction can merge, tables pile up and the engine must throttle or stall writes ("write stalls" are a classic RocksDB and Cassandra incident). Monitor the number of tables per level and the pending compaction bytes.
- Space can spike during a compaction (old and new tables exist together); you need free disk well beyond the live data size, often 50% or more for size-tiered strategies.
- Reads cost more and vary more: range scans must merge several sorted sources, and a miss can touch several tables (the filters help only for point lookups, not for ranges).
- Deletes are not immediate. A tombstone must travel down to the last level before the space returns, and many tombstones in a range make scans slow (a known problem in Cassandra).
- Write amplification still exists, and on SSDs it costs lifetime; it is only lower than in the naive B-tree, not zero.
4. Choosing between them
| B-tree | LSM tree | |
|---|---|---|
| Write path | in-place page updates, plus a WAL | sequential: log, memtable, flush, compaction |
| Write amplification | high for small random writes (about 40 in the toy), lower with batching | lower, tunable by the compaction strategy (3 to 13 in the toy) |
| Point reads | predictable: about 3 to 4 pages, usually one disk read | several tables, rescued by Bloom filters |
| Range scans | excellent: follow the leaf links | merge several sorted sources, still sequential |
| Space | fragmentation, pages 70% full | stale versions until compaction, temporary space during it |
| Latency | stable | good on average, with tail latency from stalls and compactions |
| Transactions and locking | mature; a row lives in one place, so locking it is simple | possible (RocksDB, CockroachDB, TiDB), but key versions live in many tables |
| Typical users | Postgres, MySQL InnoDB, SQLite, SQL Server, LMDB, most file systems | RocksDB, LevelDB, Cassandra, HBase, ScyllaDB, ClickHouse's MergeTree family (similar idea), and the storage layer of many newer SQL databases |
Rules of thumb:
- Read-heavy, mixed OLTP, many secondary indexes, range queries, strong transactional behaviour: a B-tree engine.
- Very high write rates, ingest of events or metrics, data much larger than memory, tolerance for background work: an LSM engine.
- Many systems are in between: WiredTiger (MongoDB) offers both, and engines such as Postgres can be made friendlier to write-heavy loads with batching,
HOTupdates and partitioning (see replication, partitioning and sharding). - Measure with your own workload; the theoretical amplification is easily dominated by the buffer pool size, the compaction settings and the hardware.
4.1 When the apparent winner flips
"LSM trees write faster, B-trees read faster" is a good first approximation and a bad conclusion. Four things routinely turn the result around. The first two sets of numbers are from the toy models, the SQLite rows are real SQLite, and the rest is documentation.
1. Compaction strategy and settings (toy). I wrote 60,000 new 100-byte records into a store that already held 100,000 records and counted the bytes written to storage per byte of user data:
| Engine and setting | Write amplification (toy) |
|---|---|
| B-tree, modified pages written back after every insert | 41.0 |
| B-tree, written back every 100 inserts | 40.5 |
| B-tree, written back every 10,000 inserts (a very large buffer pool) | 16.7 |
| LSM, leveled, T = 10 | 12.2 |
| LSM, leveled, T = 4 | 11.4 |
| LSM, size-tiered, T = 4 | 5.8 |
| LSM, size-tiered, T = 10 | 3.0 |
The gap between "the B-tree" and "the LSM tree" ranges from about 14 times (41.0 against 3.0) to about 1.4 times (16.7 against 12.2), depending only on two settings. Tiered compaction writes the least but leaves more tables to search (below); leveled writes more and reads less. There is no single "LSM write cost". Note also that in the toy the LSM never wrote more than the B-tree. Real engines add costs the toy leaves out (compaction competing for CPU and disk with foreground work, write stalls when compaction falls behind, the write-ahead log of both engines), and those are where real benchmarks find cases that favour the B-tree.
2. Cache size and memory (real SQLite). I inserted 300,000 rows with 92-byte values into SQLite, with the journal and fsync switched off to isolate the tree itself:
| Keys | 0.5 MB page cache | 64 MB page cache |
|---|---|---|
| sequential | about 902,000 inserts/s | about 908,000 inserts/s |
| random | about 265,000 inserts/s | about 507,000 inserts/s |
A larger cache made random inserts about 1.9 times faster and did nothing for sequential ones, because appends only ever touch the right edge of the tree. A B-tree benchmark on a data set that fits in memory therefore says little about the same tree when the data is ten times larger than memory. LSM engines have their own memory knobs (the memtable size, the block cache, the memory spent on Bloom filters), and a benchmark that fits in memory hides compaction cost for them too. Always test with data larger than RAM.
3. Key and value distribution.
- Key order (real SQLite). With the small cache, sequential keys were about 3.4 times faster than random keys (902,000 against 265,000 inserts/s), and random keys needed 8,649 pages for the same rows against 7,521 for sequential (15% more space). An LSM tree has no such penalty, because it sorts in memory before writing. That is why a random UUID as a clustered key hurts a B-tree engine and barely changes an LSM one.
- Overwrites (toy). When 200 hot keys were overwritten again and again, the LSM tree wrote only 0.2 to 1.2 bytes per byte (the memtable and the compactions throw the old versions away) against 41.0 for the B-tree written back every insert, and 2.8 even with the very large write-back interval. When every write was a new key, the LSM tree had to rewrite everything as it moved down the levels (3.0 to 12.2). The same engine looks excellent or merely good depending on how much of the data is overwritten.
- Large values (documentation). Compaction rewrites values along with keys, so an LSM tree with large values pays for them at every level. Engines such as WiscKey-style designs and RocksDB's BlobDB store large values separately and compact only the keys, which can reverse the result.
4. Workload shape.
- Absent keys and range scans (toy). With 10 bits per key, Bloom filters cut the table reads for a key that is not there from 3.9 (leveled T = 10), 6.8 (tiered T = 4) and 10.7 (tiered T = 10) to 0.03 to 0.07. But a range scan cannot use a Bloom filter: it had to read every table whose key range overlapped, 3.9, 6.8 and 10.7 tables in the same three setups, while a B-tree reads the leaf pages the range covers (about 6 for the roughly 160 records in these ranges). A scan-heavy workload can reverse the winner, and the tiered setting that wrote least is the one that reads most.
- Read-modify-write. An LSM tree's cheap "blind write" disappears if every update first reads the old value, and then the read amplification above is paid on each write.
- Deletes (documentation). A delete in an LSM tree is a tombstone that must be read past until compaction drops it; workloads that delete many rows (queues, expiring data) can slow reads until compaction catches up.
- Secondary indexes. Each index is another tree to update, in either family, so the amplification multiplies with the number of indexes (see database indexes).
How to decide. The only reliable procedure is to run the candidate engine on a copy of your own workload with data larger than memory, long enough to reach the steady state where compaction (or checkpointing) is running all the time, and to compare tail latency (p99), write, read and space amplification, and disk wear, not just throughput. Treat any single "B-tree is faster" or "LSM is faster" claim, including this guide's toy numbers, as an answer to one workload and one set of settings.
Where the ideas show up elsewhere
- A search index is the LSM idea applied to documents: immutable segments with background merges (search and full-text indexing).
- The write-ahead log is also the core of replication and of consensus: a replicated log is a WAL that many nodes agree on (consensus and Raft).
- Caching and the page cache decide how many of those page reads reach the disk (caching strategies).
- Columnar analytics stores combine a log-structured write path with sorted, compressed column files.
5. Common mistakes
- Using a random UUID as the clustered primary key of a large table in a B-tree engine, and wondering why inserts and cache hit rates degrade.
- Believing that "LSM is always faster for writes": with small data in memory, or with compaction that cannot keep up, a B-tree can win.
- Provisioning disks for the live data size only, and running out of space during compaction.
- Ignoring compaction metrics until writes stall.
- Using an LSM engine for read-modify-write or range-heavy workloads without checking read amplification.
- Deleting a lot of data in an LSM store and expecting the disk to shrink at once.
- Forgetting that every extra index is another tree to update: write amplification multiplies with the number of indexes.
6. Things to mention in an interview
- Pages and fan-out: why a B+tree is only three or four levels deep and a lookup is about one disk read.
- In-place updates, page splits, the WAL, and why a small write costs a page.
- The LSM write path (WAL, memtable, SSTable flush) and compaction with tombstones.
- Write, read and space amplification, and how leveled and size-tiered compaction trade them.
- Bloom filters and why they matter for point reads.
- Which real systems use which, and how to choose with a workload in mind.
- That sequential key order helps B-trees (full pages) and that random keys cost space and cache.
Quick recap
- A B-tree keeps sorted data in pages updated in place: shallow (about one disk read per lookup) but a small random write costs a whole page (about 40 times the data written in the toy) and random keys leave pages about 70% full.
- An LSM tree appends to a log and a memtable, flushes sorted immutable tables and merges them in the background: writes are sequential (3 to 13 times the data written in the toy), at the cost of compaction work, extra space and more places to read.
- Bloom filters cut the reads for a missing key from 4 to 22 tables to nearly zero.
- Leveled compaction reads less and uses less space; size-tiered writes less.
- Choose by workload: B-tree for read-heavy and transactional work, LSM for write-heavy ingest, and measure compaction and stalls if you pick the second.
Appendix: the experiment code
Both scripts are Python 3 with the standard library only. The first measures SQLite (a B-tree) and raw disk writes on a small virtual machine, so its absolute numbers depend on the machine and vary between runs. The second is a model, not a database: it counts entries and pages instead of storing bytes, uses a fixed random seed, and prints exactly the tables above. Its LSM tree merges whole levels (real engines compact individual files), counts every entry as one 100-byte record, and stands in a Bloom filter with a real bit array of 10 bits per key. Treat its amplification figures as illustrations of the trade-offs and not as predictions for RocksDB or Cassandra.
SQLite as a real B-tree, and sequential against random disk writes
import sqlite3, os, random, time, hashlib
def run(kind, n=300_000):
path = f"/var/tmp/lsm/{kind}.db"
for ext in ("", "-wal", "-journal"):
if os.path.exists(path + ext): os.remove(path + ext)
db = sqlite3.connect(path); db.execute("pragma journal_mode=off"); db.execute("pragma synchronous=off"); db.execute("pragma cache_size=-2048") # a 2 MB page cache
db.execute("create table t(k text primary key, v text) without rowid")
keys = [f"{i:012d}" for i in range(n)] if kind == "sequential" else [hashlib.md5(str(i).encode()).hexdigest()[:12] for i in range(n)]
payload = "x" * 80
t0 = time.perf_counter()
for i in range(0, n, 10000):
db.executemany("insert into t values (?,?)", [(k, payload) for k in keys[i:i+10000]]); db.commit()
dt = time.perf_counter() - t0
pages = db.execute("pragma page_count").fetchone()[0]; ps = db.execute("pragma page_size").fetchone()[0]
raw = n * (12 + 80)
rnd = random.Random(1); probe = [rnd.choice(keys) for _ in range(20000)]
t1 = time.perf_counter()
for k in probe: db.execute("select v from t where k=?", (k,)).fetchone()
lt = time.perf_counter() - t1
return f"{kind:>10}: {n/dt:>9,.0f} inserts/s, file {pages*ps/1e6:5.1f} MB for {raw/1e6:4.1f} MB of data (x{pages*ps/raw:.2f}), {20000/lt:>8,.0f} lookups/s"
print("SQLite (a B-tree), page size 4096, 2 MB cache, 300,000 rows of 92 bytes:")
for kind in ("sequential", "random"): print(" ", run(kind))
# raw disk: appending 4 KB blocks against rewriting random blocks of a 1 GB file, flushing every 64 writes
def disk(kind, n=20000, size=1 << 30):
path = "/var/tmp/lsm/blob";
fd = os.open(path, os.O_RDWR | os.O_CREAT); os.ftruncate(fd, size); buf = os.urandom(4096); rnd = random.Random(2)
t = time.perf_counter()
for i in range(n):
off = i * 4096 if kind == "append" else rnd.randrange(size // 4096) * 4096
os.pwrite(fd, buf, off)
if i % 64 == 63: os.fdatasync(fd)
dt = time.perf_counter() - t; os.close(fd); os.remove(path); return n * 4096 / dt / 1e6
print(f"4 KB writes with an fdatasync every 64 writes: append {disk('append'):.0f} MB/s, random in place {disk('random'):.0f} MB/s")
A toy B+tree and a toy LSM tree with Bloom filters
import bisect, random, math, hashlib
# ===================== a toy B+tree: leaves hold up to LEAF records (a 4 KB page of ~100-byte records) =====================
LEAF = 40
class BPlusLeafs:
"""Only the leaf level matters for the questions below, so the interior is a sorted list of leaf minimums."""
def __init__(self): self.leaves = [[]]; self.mins = [None]; self.splits = 0
def find(self, k): return max(0, bisect.bisect_right(self.mins[1:], k)) if len(self.leaves) > 1 else 0
def insert(self, k):
i = self.find(k); leaf = self.leaves[i]; bisect.insort(leaf, k); touched = {i}
if len(leaf) > LEAF:
if i == len(self.leaves) - 1 and k == leaf[-1]: # appending at the right edge: split off just the new record
new = [leaf.pop()]
else: # otherwise split in half
half = len(leaf) // 2; new = leaf[half:]; del leaf[half:]
self.leaves.insert(i + 1, new); self.mins.insert(i + 1, new[0]); self.splits += 1; touched.add(i + 1)
return touched
def fill(self): return sum(map(len, self.leaves)) / (len(self.leaves) * LEAF)
def btree_experiment(n=100_000):
print("B+tree leaf pages, 100,000 inserts, 40 records per page:")
for kind in ("sequential", "random"):
t = BPlusLeafs(); keys = list(range(n)) if kind == "sequential" else random.Random(5).sample(range(10**9), n)
for k in keys: t.insert(k)
print(f" {kind:>10} keys: {len(t.leaves):>5} leaf pages, average fill {t.fill()*100:.0f}%, {t.splits} page splits")
# write amplification: after every `batch` inserts all modified pages are written back in full (4096 bytes)
print("page writes per record, when modified pages are written back after every `batch` inserts (record = 100 bytes, page = 4096 bytes):")
keys = random.Random(7).sample(range(10**9), 200_000)
t = BPlusLeafs()
for k in keys[:100_000]: t.insert(k) # a tree that already holds 100,000 records
for batch in (1, 10, 100, 1000, 10000):
dirty = set(); writes = 0; n_ins = 0
for k in keys[100_000:100_000 + 20_000]:
# a split moves page numbers, so count by id of the page object
i = t.find(k); leaf = t.leaves[i]; before = id(leaf)
t.insert(k); dirty.add(before); n_ins += 1
if n_ins % batch == 0: writes += len(dirty); dirty = set()
writes += len(dirty)
print(f" batch {batch:>5}: {writes/n_ins:5.2f} page writes per inserted record = {writes*4096/(n_ins*100):6.1f} bytes written per byte of data")
# ===================== a toy LSM tree =====================
class Bloom:
def __init__(self, n, bits_per_key=10):
self.m = max(8, n * bits_per_key); self.k = max(1, round(bits_per_key * math.log(2))); self.bits = bytearray(self.m // 8 + 1)
def _h(self, x):
d = hashlib.blake2b(str(x).encode(), digest_size=16).digest(); a = int.from_bytes(d[:8], "big"); b = int.from_bytes(d[8:], "big") | 1
return ((a + i * b) % self.m for i in range(self.k))
def add(self, x):
for h in self._h(x): self.bits[h >> 3] |= 1 << (h & 7)
def __contains__(self, x): return all(self.bits[h >> 3] & (1 << (h & 7)) for h in self._h(x))
class Table:
def __init__(self, keys, bloom_bits):
self.keys = sorted(set(keys)); self.bloom = Bloom(len(self.keys), bloom_bits) if bloom_bits else None
for k in self.keys: self.bloom and self.bloom.add(k)
class LSM:
"""Entries are keys only (every key is a 100-byte record). `written` counts every entry written to 'disk' by flushes and compactions."""
def __init__(self, strategy, T=10, mem=200, bloom_bits=10):
self.strategy, self.T, self.mem, self.bits = strategy, T, mem, bloom_bits
self.memtable = set(); self.levels = [[]]; self.written = 0; self.user = 0
def put(self, k):
self.memtable.add(k); self.user += 1
if len(self.memtable) >= self.mem: self.flush()
def flush(self):
t = Table(self.memtable, self.bits); self.memtable = set(); self.written += len(t.keys)
self.levels[0].append(t); self.compact()
def merge(self, tables):
keys = set(); [keys.update(t.keys) for t in tables]
out = Table(keys, self.bits); self.written += len(out.keys); return out
def compact(self):
if self.strategy == "tiered":
lvl = 0
while lvl < len(self.levels) and len(self.levels[lvl]) >= self.T:
merged = self.merge(self.levels[lvl]); self.levels[lvl] = []
if lvl + 1 == len(self.levels): self.levels.append([])
self.levels[lvl + 1].append(merged); lvl += 1
else: # leveled: level 0 collects up to 4 tables; level i >= 1 is one sorted run holding at most mem * 4 * T**i entries
if len(self.levels[0]) >= 4:
self.push(0)
lvl = 1
while lvl < len(self.levels) and self.levels[lvl] and len(self.levels[lvl][0].keys) > self.mem * 4 * self.T ** lvl:
self.push(lvl); lvl += 1
def push(self, lvl):
if lvl + 1 == len(self.levels): self.levels.append([])
merged = self.merge(self.levels[lvl] + self.levels[lvl + 1]); self.levels[lvl] = []; self.levels[lvl + 1] = [merged]
def get(self, k):
"""Returns (found, tables whose data had to be read)."""
if k in self.memtable: return True, 0
reads = 0
for lvl in self.levels:
for t in reversed(lvl):
if t.bloom is not None and k not in t.bloom: continue
reads += 1 # read the table (a disk read)
if bisect.bisect_left(t.keys, k) < len(t.keys) and t.keys[bisect.bisect_left(t.keys, k)] == k: return True, reads
return False, reads
def tables(self): return sum(len(l) for l in self.levels)
def stored(self): return sum(len(t.keys) for l in self.levels for t in l)
def lsm_experiment(n=300_000):
print(f"LSM tree, {n:,} random writes to 100,000 distinct keys (so keys are overwritten about 3 times), memtable of 200 entries:")
rnd = random.Random(9); space_keys = [rnd.randrange(10**12) for _ in range(100_000)]; keys = [rnd.choice(space_keys) for _ in range(n)]
absent = [rnd.randrange(10**12) for _ in range(2000)]
for strategy, T in (("leveled", 10), ("leveled", 4), ("tiered", 4), ("tiered", 10)):
for bits in (0, 10):
db = LSM(strategy, T, bloom_bits=bits)
for k in keys: db.put(k)
present = [rnd.choice(keys) for _ in range(2000)]
rp = sum(db.get(k)[1] for k in present) / 2000; ra = sum(db.get(k)[1] for k in absent) / 2000
if bits == 0 or True:
print(f" {strategy:>7} T={T:>2} bloom={'on ' if bits else 'off'}: {db.tables():>2} tables, write amplification {db.written/db.user:5.1f}, space {db.stored()/len(set(keys)):.2f}x, table reads per lookup: present {rp:4.1f}, absent {ra:4.2f}")
def lsm_vs_btree_bytes():
print("bytes written to storage per byte of user data (random inserts, 100-byte records, 4 KB pages):")
print(" B-tree, write-back after every insert: 4096/100 = 41 bytes (plus the write-ahead log)")
print(" B-tree, one write-back per 1,000 inserts into 100,000 leaf pages: see the table above")
if __name__ == "__main__":
btree_experiment(); lsm_experiment()
When the winner flips: SQLite with different caches and key orders, and the toy models with different settings
Save the toy script from the previous appendix section as toy.py (it only defines classes when imported), and this one as reversal.py in the same folder. Part 1 needs only the standard library's sqlite3; its timings vary by machine. Part 2 uses the toy models, so it counts entries and pages and stores no data.
"""When does the apparent winner between a B-tree and an LSM tree flip?
Part 1 uses SQLite, a real B-tree. Part 2 uses the toy models from the other script (toy.py): they count entries and pages,
they are not databases, so their numbers show the direction of an effect and not the speed of any real engine."""
import os, random, sqlite3, time, bisect
import toy
# ---------------------------------------------------------------- part 1: real SQLite
def sqlite_insert(keys, cache_kb, path="/tmp/rev.db"):
for ext in ("", "-journal", "-wal"):
try: os.remove(path + ext)
except FileNotFoundError: pass
db = sqlite3.connect(path)
db.execute("pragma journal_mode=off"); db.execute("pragma synchronous=off"); db.execute(f"pragma cache_size=-{cache_kb}")
db.execute("create table t(k integer primary key, v blob)")
v = b"x" * 92
t = time.perf_counter()
db.executemany("insert into t values (?, ?)", ((k, v) for k in keys))
db.commit(); dt = time.perf_counter() - t
pages = db.execute("pragma page_count").fetchone()[0]; db.close(); os.remove(path)
return dt, pages
def part1(n=300_000):
rnd = random.Random(1)
seq = list(range(n)); rand = rnd.sample(range(10**9), n)
print(f"SQLite (a real B-tree), {n:,} inserts of 92-byte values, journal and fsync off to isolate the tree itself:")
for label, keys in (("sequential keys", seq), ("random keys", rand)):
for kb in (512, 65_536):
dt, pages = sqlite_insert(keys, kb)
print(f" {label:>15}, page cache {kb//1024 if kb >= 1024 else 0.5:>4} MB: {n/dt:>9,.0f} inserts/s, {pages:,} pages in the file")
# ---------------------------------------------------------------- part 2: toy models
def btree_write_amp(keys, preload, batch):
"""Page writes (4096 bytes) per 100-byte record when dirty pages are written back every `batch` inserts."""
t = toy.BPlusLeafs()
for k in preload: t.insert(k)
dirty, writes, n = set(), 0, 0
for k in keys:
before = id(t.leaves[t.find(k)]); t.insert(k); dirty.add(before); n += 1
if n % batch == 0: writes += len(dirty); dirty = set()
writes += len(dirty)
return writes * 4096 / (n * 100)
def lsm_run(keys, strategy, T, bits=10, preload=(), checkpoints=None, probe=None):
"""Loads `preload` first (a store that already holds data), then counts only the writes made for `keys`."""
db = toy.LSM(strategy, T, bloom_bits=bits)
for k in preload: db.put(k)
db.written, db.user = 0, 0
samples = []
for n, k in enumerate(keys, 1):
db.put(k)
if checkpoints and n in checkpoints: samples.append(probe(db))
return db, samples
def scan_tables(db, lo, hi):
"""Tables whose key range overlaps [lo, hi]: every one of them has to be read for a range scan (a Bloom filter cannot help)."""
c = 0
for lvl in db.levels:
for t in lvl:
if t.keys and t.keys[0] <= hi and t.keys[-1] >= lo: c += 1
return c
def part2():
rnd = random.Random(3)
W = 60_000 # writes measured, on top of a store that already holds 100,000 records
pre = rnd.sample(range(10**12), 100_000)
hot_space = rnd.sample(pre, 200) # 200 keys that already exist
workloads = {
"every write is a new key": [rnd.randrange(10**12) for _ in range(W)],
"200 hot keys overwritten again and again": [rnd.choice(hot_space) for _ in range(W)],
}
print(f"\nToy models: {W:,} writes of 100-byte records into a store that already holds {len(pre):,} records")
print(" (a) write amplification = bytes written to storage per byte the application wrote (the B-tree figure excludes its write-ahead log)")
for name, keys in workloads.items():
row = [f"B-tree write-back every {b:>6}: {btree_write_amp(keys, pre, b):5.1f}" for b in (1, 100, 10_000)]
row += [f"LSM {s} T={T}: {lsm_run(keys, s, T, preload=pre)[0].written / len(keys):4.1f}" for s, T in (("leveled", 10), ("leveled", 4), ("tiered", 4), ("tiered", 10))]
print(f" {name}\n " + "\n ".join(row))
print(" (b) read side after loading new keys; averaged over 10 checkpoints, because the number of tables rises and falls as compactions run")
keys = workloads["every write is a new key"]
absent = [rnd.randrange(10**12) for _ in range(500)]
cps = set(range(W // 10, W + 1, W // 10))
def probe(db):
ra = sum(db.get(k)[1] for k in absent) / len(absent)
starts = [rnd.randrange(10**12) for _ in range(100)]
return db.tables(), ra, sum(scan_tables(db, a, a + 10**9) for a in starts) / 100
for s, T in (("leveled", 10), ("tiered", 4), ("tiered", 10)):
for bits in (0, 10):
_, smp = lsm_run(keys, s, T, bits, preload=pre, checkpoints=cps, probe=probe)
m = lambda i: sum(x[i] for x in smp) / len(smp)
print(f" LSM {s:>7} T={T:>2} bloom={'on ' if bits else 'off'}: {m(0):4.1f} tables on average (max {max(x[0] for x in smp)}), reads for an absent key {m(1):5.2f}, tables to read for a short range {m(2):4.1f}")
print(" B-tree: a lookup reads 3 to 4 pages (the upper levels are cached); a range scan reads the leaf pages it covers")
if __name__ == "__main__":
part1(); part2()
Sources
- Patrick O'Neil, Edward Cheng, Dieter Gawlick and Elizabeth O'Neil, The Log-Structured Merge-Tree (LSM-Tree) (Acta Informatica, 1996).
- Fay Chang et al., Bigtable: A Distributed Storage System for Structured Data (OSDI 2006), which popularised memtables and SSTables.
- Martin Kleppmann, Designing Data-Intensive Applications (O'Reilly), chapter 3, "Storage and Retrieval".
- Manos Athanassoulis et al., Designing Access Methods: The RUM Conjecture (EDBT 2016).
- The RocksDB wiki: leveled and universal compaction, write amplification, Bloom filters and write stalls.
- Alex Petrov, Database Internals (O'Reilly), parts on B-tree variants and LSM storage.
- The SQLite file format documentation and the PostgreSQL documentation chapter on write-ahead logging.
- Manos Athanassoulis et al., Designing Access Methods: The RUM Conjecture (EDBT 2016); Niv Dayan and Stratos Idreos, Dostoevsky: Better Space-Time Trade-Offs for LSM-Tree Based Key-Value Stores (SIGMOD 2018), on how compaction policy moves the trade-off.
- Lanyue Lu et al., WiscKey: Separating Keys from Values in SSD-conscious Storage (FAST 2016), and the RocksDB wiki pages on compaction and BlobDB.
Practise this topic: Databases