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:

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 orderLeaf pagesAverage fillSplits
sequential keys2,500100%2,499
random keys3,57470%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 everyPage writes per recordBytes written per byte of data
1 insert1.0041.0
10 inserts1.0040.9
100 inserts0.9940.6
1,000 inserts0.9338.0
10,000 inserts0.5622.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

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

  1. A write is appended to a log (for durability) and inserted into an in-memory sorted structure, the memtable.
  2. 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.
  3. Tables accumulate. A read must check the memtable and then the tables, newest first, because a newer version of a key hides older ones.
  4. 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:

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):

StrategyTablesWrite amplificationSpaceTable reads per lookup, key present (no filter / filter)Table reads, key absent (no filter / filter)
leveled, T = 10412.81.63x3.1 / 1.04.00 / 0.03
leveled, T = 469.11.48x5.2 / 1.06.00 / 0.05
size-tiered, T = 4104.91.77x8.1 / 1.110.00 / 0.08
size-tiered, T = 10223.11.88x18.3 / 1.122.00 / 0.19

Read it from left to right:

(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

4. Choosing between them

B-treeLSM tree
Write pathin-place page updates, plus a WALsequential: log, memtable, flush, compaction
Write amplificationhigh for small random writes (about 40 in the toy), lower with batchinglower, tunable by the compaction strategy (3 to 13 in the toy)
Point readspredictable: about 3 to 4 pages, usually one disk readseveral tables, rescued by Bloom filters
Range scansexcellent: follow the leaf linksmerge several sorted sources, still sequential
Spacefragmentation, pages 70% fullstale versions until compaction, temporary space during it
Latencystablegood on average, with tail latency from stalls and compactions
Transactions and lockingmature; a row lives in one place, so locking it is simplepossible (RocksDB, CockroachDB, TiDB), but key versions live in many tables
Typical usersPostgres, MySQL InnoDB, SQLite, SQL Server, LMDB, most file systemsRocksDB, LevelDB, Cassandra, HBase, ScyllaDB, ClickHouse's MergeTree family (similar idea), and the storage layer of many newer SQL databases

Rules of thumb:

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 settingWrite amplification (toy)
B-tree, modified pages written back after every insert41.0
B-tree, written back every 100 inserts40.5
B-tree, written back every 10,000 inserts (a very large buffer pool)16.7
LSM, leveled, T = 1012.2
LSM, leveled, T = 411.4
LSM, size-tiered, T = 45.8
LSM, size-tiered, T = 103.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:

Keys0.5 MB page cache64 MB page cache
sequentialabout 902,000 inserts/sabout 908,000 inserts/s
randomabout 265,000 inserts/sabout 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.

4. Workload shape.

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

5. Common mistakes

6. Things to mention in an interview

Quick recap

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

Practise this topic: Databases

More guides