Storage Structures: B+ Trees, Skip Lists and LSM Trees
After this lesson, you will be able to:
- Explain why the cost of a disk-based structure is counted in block reads, and why that makes wide, shallow trees win
- Build a B+ tree level by level, look up a key, split a full leaf, and compute the height from the fan-out
- Write a skip list with seeded random levels, count its search steps, and explain why the expected cost is O(log n)
- Write a write-ahead log with checksums and replay it after a crash
- Build a tiny LSM tree with a memtable, sorted runs, tombstones, per-run Bloom filters and compaction, and read its write and read costs
- Choose between a B+ tree and an LSM tree for a workload, and say when neither is needed
Before You Start
#Why Disks Change the Rules
Every cost in the earlier lessons counted steps in memory. Memory is fast, but it is small and it forgets everything when the power goes off. A disk, whether spinning or solid-state, holds far more, keeps data safely, and is much slower to reach. So a program that stores data for good must work around the disk.
We will not quote timings, because they change across machines and years. We only rely on the direction. Fewer block reads is better, and sequential beats random.
#Wide Beats Deep: Counting Block Reads
Start with the plain method: keep the entries sorted in a file and run binary search. Each probe lands in some block and costs one read, and binary search needs about log2 of the number of blocks. For a billion entries that is still around two dozen reads, and each may be random.
Now ask for more from each read. A block holds many entries, so one read can cut the range into B pieces, not just two. The reads drop from log base 2 to log base B. Since log_B n = log2 n / log2 B, a B near a hundred cuts the reads by a factor of about seven. That is the whole idea of a B-tree. The rest is keeping it correct as data changes.
fanout entries. The leaves need ceil(n / fanout) blocks, the level above needs one entry per leaf block, and so on until one block is left.Each block holds 100 entries. Keys are kept in a tree where every block has 100 entries and one block per level is read. About how many levels (and so block reads) does it take to find one key among a billion?
import math
def tree_levels(n_keys, fanout):
"""Levels of a tree where each block holds `fanout` entries. O(log_fanout n) time."""
levels, pages = 0, n_keys
while pages > 0:
pages = math.ceil(pages / fanout) # blocks needed at this level
levels += 1
if pages == 1:
break
return levels
def binary_reads(n_keys, fanout):
"""Worst-case block reads for binary search over sorted blocks."""
reads, lo, hi = 0, 0, math.ceil(n_keys / fanout) - 1
while lo <= hi:
mid = (lo + hi) // 2
reads += 1
lo = mid + 1 # worst case: always search the right half
return reads
for n in (10_000, 1_000_000, 1_000_000_000):
print(n, binary_reads(n, 100), tree_levels(n, 100))
# Output:
# 10000 7 2
# 1000000 14 3
# 1000000000 24 5fanout entries. A half-empty block makes the tree taller, which is why the structures below work to keep blocks mostly full.#The B+ Tree as an Index
Take 100,000 even numbers and 100 entries per block. The leaf level has 1,000 blocks. The level above holds the first key of each leaf, so 1,000 separators fill 10 blocks, and a root of 10 separators sits on top. To find a key, read the root, pick the child whose range holds the key, and repeat down to a leaf. That is one read per level.
The code below builds that tree from sorted keys, and a lookup counts its reads. A real tree is built by inserts, and the next section shows that. Building from sorted data is simpler and shows the shape.
from bisect import bisect_right
def build_levels(keys, page_size):
"""Static B+ tree. levels[0] is the leaf pages. Each level above holds the first
key of every page below it. Returns the levels, top level last. O(n) time and space."""
levels = [[keys[i:i + page_size] for i in range(0, len(keys), page_size)]]
while len(levels[-1]) > 1:
firsts = [page[0] for page in levels[-1]]
levels.append([firsts[i:i + page_size] for i in range(0, len(firsts), page_size)])
return levels
def lookup(levels, page_size, key):
"""Return (found, page_reads): one read per level. O(log_B n) reads."""
reads, idx = 0, 0
for level in range(len(levels) - 1, 0, -1):
page = levels[level][idx]
reads += 1
slot = max(bisect_right(page, key) - 1, 0) # which child covers this key
idx = idx * page_size + slot
leaf = levels[0][idx]
reads += 1
pos = bisect_right(leaf, key) - 1
return (pos >= 0 and leaf[pos] == key), reads
keys = list(range(0, 200_000, 2)) # 100,000 even numbers
levels = build_levels(keys, 100)
print([len(level) for level in levels])
print(lookup(levels, 100, 77_776), lookup(levels, 100, 77_777), lookup(levels, 100, -5))
print(lookup(levels, 100, 199_998))
# Output:
# [1000, 10, 1]
# (True, 3) (False, 3) (False, 3)
# (True, 3)bisect_right, which is free in this model because the block is already in memory.A B+ tree with 100 separators per block holds 100,000 keys and has 3 levels. You double the data to 200,000 keys. Roughly how many levels does it need now?
#How a B+ Tree Grows: Splits
Real data arrives one key at a time. The tree must stay correct and stay shallow without being rebuilt. The trick is that a block is allowed to be anywhere from half full to full, and only a full block ever changes shape.
If the parent was full too, it splits the same way, and the split can climb to the root. When the root splits, a new root appears above it and the tree grows one level taller.
Look at a leaf that holds at most four keys. Adding 25 to [10, 20, 30] just fits and gives [10, 20, 25, 30]. Adding 40 to that block makes five keys, which is too many. The split makes [10, 20] and [25, 30, 40], and 25 goes up as the separator. In a B+ tree 25 stays in the right leaf, because the leaves must hold every key.
def insert_leaf(leaf, key, max_keys):
"""Insert key into a sorted leaf. If it overflows, split it in half and return
(left, separator, right); otherwise return the new leaf. O(max_keys) time."""
new = sorted(leaf + [key])
if len(new) <= max_keys:
return new
mid = len(new) // 2
return new[:mid], new[mid], new[mid:] # the separator is copied up, not moved
print(insert_leaf([10, 20, 30], 25, 4))
print(insert_leaf([10, 20, 25, 30], 40, 4))
# Output:
# [10, 20, 25, 30]
# ([10, 20], 25, [25, 30, 40])Why does this keep the tree healthy? Three invariants do the work. An invariant is a fact that holds before and after every operation. First, all leaves stay at one depth, because the tree grows only at the top, which lifts every leaf together.
Second, every block except the root is at least half full, because a split of a full block gives two halves. Third, keys inside a block are sorted and the separators bracket the child ranges, so a lookup never goes the wrong way.
The second invariant gives the height bound. If every block has at least B / 2 children, the tree widens by a factor of at least B / 2 per level, so n keys need at most about log base (B / 2) of n levels. That is still O(log_B n), because changing the base by a factor of two changes the log by only a small constant.
Why do databases use this shape? One block read is the unit of cost, and a B+ tree uses one block per level. Reads are few, the keys are in sorted order for ranges, and updates touch only a few blocks near the leaf. For example, SQLite and many other relational databases store their indexes as B-tree family structures, and some use them for the tables themselves.
#Skip Lists: Balance from Coin Flips
To search, start at the top level and move right while the next key is smaller than the target, then drop one level and repeat. At level 0 you land next to the key.
random.Random(seed), so one seed builds the same list every run, which keeps tests repeatable. The code counts each move right and each drop down as one step.import random
class SkipNode:
def __init__(self, key, height):
self.key = key
self.next = [None] * height # next[i] = following node on level i
class SkipList:
"""Sorted set. Expected O(log n) search and insert, expected O(n) space."""
def __init__(self, seed=7, max_height=16):
self.rng = random.Random(seed) # seeded, so every run builds the same list
self.max_height = max_height
self.head = SkipNode(None, max_height)
self.height = 1 # levels currently in use
self.steps = 0 # moves made by the last operation
def _random_height(self):
h = 1
while h < self.max_height and self.rng.random() < 0.5:
h += 1
return h
def _find_before(self, key):
"""Last node with a key below `key` on every level."""
update = [self.head] * self.max_height
node = self.head
for level in range(self.height - 1, -1, -1):
while node.next[level] is not None and node.next[level].key < key:
node = node.next[level] # move right
self.steps += 1
update[level] = node # then drop down
self.steps += 1
return update
def contains(self, key):
self.steps = 0
node = self._find_before(key)[0].next[0]
return node is not None and node.key == key
def insert(self, key):
self.steps = 0
update = self._find_before(key)
nxt = update[0].next[0]
if nxt is not None and nxt.key == key:
return False
h = self._random_height()
self.height = max(self.height, h)
node = SkipNode(key, h)
for level in range(h):
node.next[level] = update[level].next[level]
update[level].next[level] = node
return True
def levels(self):
"""Keys on each level, bottom first."""
out = []
for level in range(self.height):
row, node = [], self.head.next[level]
while node is not None:
row.append(node.key)
node = node.next[level]
out.append(row)
return out
s = SkipList(seed=7)
for k in [3, 6, 7, 9, 12, 17, 19, 21, 25, 26]:
s.insert(k)
for row in reversed(s.levels()):
print(row)
print(s.contains(19), s.steps, s.contains(20), s.steps)
# Output:
# [9]
# [9, 26]
# [9, 26]
# [3, 7, 9, 12, 26]
# [3, 6, 7, 9, 12, 21, 25, 26]
# [3, 6, 7, 9, 12, 17, 19, 21, 25, 26]
# True 9 False 10Read the lists from the top lane down. Searching for 19 starts at the head of the top lane, moves to 9, and drops. The next two lanes show 26 after 9, too big, so it drops twice more. In the lane [3, 7, 9, 12, 26] it moves to 12 and drops. In the bottom lane it moves to 17, and the next key is 19. That is 9 steps, the number printed after True.
Now the important test. Insert 4,096 keys in sorted order, the input that ruins a plain binary search tree, and measure.
A skip list with seed 1 gets the keys 0 to 4095 inserted in increasing order. We then search for every 7th key and average the steps (each move right or drop down is one step). A plain linked list would average about 2,048 steps. What does the skip list average?
big = SkipList(seed=1)
n = 4096
for k in range(n): # sorted input: the worst case for a plain BST
big.insert(k)
print(big.height, [len(r) for r in big.levels()][:6])
total, queries = 0, 0
for k in range(0, n, 7):
big.contains(k)
total += big.steps
queries += 1
print(round(total / queries, 1), "average steps; a plain list averages about", n // 2)
# Output:
# 14 [4096, 2054, 991, 501, 258, 133]
# 26.1 average steps; a plain list averages about 2048The levels shrink by about half each time (4096, 2054, 991, ...), as the coin flips promise. Here is why the cost is O(log n) in expectation. Walk the search path backward, from the found node up to the top. At each node you either go up, if it is the top of a taller tower, or go left. Each case has probability one half.
You need about log2 n upward moves to reach the top, and each costs two backward steps on average. So the expected path is about 2 log2 n. For n = 4096 that is 24, close to the 26.1 measured.
The space is O(n) in expectation, because a node has an expected height of 2, so n nodes hold about 2n pointers. Two assumptions carry the proof. The coin flips must be independent of the keys, and nobody can see them and craft input against them. A fixed seed is fine for tests and bad for a hostile service. The worst case is O(n), with tiny probability.
Compared with a balanced tree, a skip list is short to write and has no rotations. Its inserts change only a few pointers, which suits concurrent updates. For example, Redis sorted sets are built on skip lists. The costs are extra pointers and many small memory jumps, which suit memory better than disk.
#The Write-Ahead Log
Memory forgets when the power goes out. A structure that holds the only copy of an acknowledged write will lose it in a crash. Writing the whole structure to disk after every change is far too slow.
The rule is "log first, then apply". If the machine dies, restart reads the log from the start and applies each record again, which rebuilds the lost state. Once the changes are safely in the main structure, the log before that point is no longer needed and can be trimmed. That trim is called a checkpoint.
zlib.crc32, which gives the same numbers on every run.from zlib import crc32
def encode(key, value):
body = f"{key}={value}"
return f"{crc32(body.encode()):08x}:{body}"
def replay(lines):
"""Rebuild state from log lines. Stop at the first record whose checksum fails.
O(total log length) time."""
state = {}
for line in lines:
checksum, _, body = line.partition(":")
if f"{crc32(body.encode()):08x}" != checksum:
break # a half-written record: nothing after it can be trusted
key, _, value = body.partition("=")
state[key] = value
return state
log = [encode("a", 1), encode("b", 2), encode("a", 3)]
print(log[0])
print(replay(log))
torn = log + [encode("c", 4)[:-2]] # the crash cut the last record short
print(replay(torn))
# Output:
# 8d623081:a=1
# {'a': '3', 'b': '2'}
# {'a': '3', 'b': '2'}fsync in many systems. Without it the data may sit in an operating-system buffer.B+ tree databases keep a WAL too, because changing a page in place is not crash-safe. For example, PostgreSQL has a write-ahead log. In an LSM tree the log matters for another reason: the memory table holds the newest data.
#Log-Structured Merge Trees
Here each run keeps its own filter, and a lookup skips any run whose filter says no. The filters are small enough to stay in memory.
from bisect import bisect_left
from zlib import crc32
TOMB = "<deleted>" # marks a deleted key
class Bloom:
"""A tiny Bloom filter: 'definitely absent' or 'maybe present'."""
def __init__(self, keys, bits_per_key=10, hashes=3):
self.m = max(8, bits_per_key * len(keys))
self.hashes = hashes
self.bits = 0
for key in keys:
for pos in self._positions(key):
self.bits |= 1 << pos
def _positions(self, key):
raw = key.encode()
h1, h2 = crc32(raw), crc32(raw[::-1] + b"#") | 1
return [(h1 + i * h2) % self.m for i in range(self.hashes)]
def maybe_has(self, key):
return all(self.bits >> pos & 1 for pos in self._positions(key))
class Run:
"""An immutable sorted run: parallel lists of keys and values, plus a Bloom filter."""
def __init__(self, items):
self.keys = [k for k, _ in items]
self.values = [v for _, v in items]
self.bloom = Bloom(self.keys)
def find(self, key):
i = bisect_left(self.keys, key) # binary search inside the run
if i < len(self.keys) and self.keys[i] == key:
return True, self.values[i]
return False, None
class TinyLSM:
def __init__(self, memtable_limit=4, max_runs=3):
self.memtable = {}
self.runs = [] # newest first
self.wal = [] # records not yet safe in a run
self.limit, self.max_runs = memtable_limit, max_runs
self.puts = 0
self.entries_written = 0 # entries written to runs (flush + compaction)
self.run_probes = 0 # runs actually searched by get()
self.bloom_skips = 0 # runs skipped thanks to a Bloom filter
def put(self, key, value):
self.wal.append((key, value)) # 1. log first
self.memtable[key] = value # 2. then memory
self.puts += 1
if len(self.memtable) >= self.limit:
self.flush()
def delete(self, key):
self.put(key, TOMB) # a delete is a write of a marker
def flush(self):
items = sorted(self.memtable.items())
self.runs.insert(0, Run(items))
self.entries_written += len(items)
self.memtable, self.wal = {}, [] # these entries are in a run now, drop the log
if len(self.runs) > self.max_runs:
self.compact()
def get(self, key):
if key in self.memtable:
v = self.memtable[key]
return None if v == TOMB else v
for run in self.runs: # newest to oldest: the first hit wins
if not run.bloom.maybe_has(key):
self.bloom_skips += 1
continue
self.run_probes += 1
found, v = run.find(key)
if found:
return None if v == TOMB else v
return None
def compact(self):
"""Merge every run into one. Newest value wins; tombstones can be dropped
because nothing older is left for them to hide."""
merged = {}
for run in reversed(self.runs): # oldest first, so newer values overwrite
for k, v in zip(run.keys, run.values):
merged[k] = v
items = sorted((k, v) for k, v in merged.items() if v != TOMB)
self.runs = [Run(items)] if items else []
self.entries_written += len(items)
def recover(self):
"""Rebuild the memtable from the log, as after a crash."""
self.memtable = {}
for key, value in self.wal:
self.memtable[key] = value
db = TinyLSM()
for i, name in enumerate(["ant", "bee", "cat", "dog", "eel", "fox", "gnu", "hen"]):
db.put(name, i)
db.put("ant", 100)
db.delete("bee")
print(len(db.runs), db.memtable, db.wal)
print(db.get("ant"), db.get("bee"), db.get("cat"), db.get("zzz"))
print([r.keys for r in db.runs])
# Output:
# 2 {'ant': 100, 'bee': '<deleted>'} [('ant', 100), ('bee', '<deleted>')]
# 100 None 2 None
# [['eel', 'fox', 'gnu', 'hen'], ['ant', 'bee', 'cat', 'dog']]get("ant") returns 100 and not the old 0 from the older run, and bee reads as missing even though the old run still holds it. The log holds only the two records that are not yet in a run. If the process died now, recover would rebuild the memtable from them.Now the costs. A put does one log append and one memory insert, and a flush writes a run in one sequential pass. A get checks the memtable and then up to R runs, each with a binary search, so without filters a miss costs R block reads. The next cell runs 64 puts, then 64 lookups of keys that are not there.
The store has memtable limit 4 and at most 4 runs, and after 64 puts of distinct keys it holds 4 runs. Each run has a Bloom filter. We look up 64 keys that were never stored. Each lookup could search up to 4 runs, so 256 searches are possible. How many runs are actually searched?
db2 = TinyLSM(memtable_limit=4, max_runs=4)
for i in range(64):
db2.put(f"k{i * 37 % 64:02d}", i)
print(len(db2.runs), [len(r.keys) for r in db2.runs])
print("puts", db2.puts, "entries written", db2.entries_written,
"per put", round(db2.entries_written / db2.puts, 2))
db2.run_probes = db2.bloom_skips = 0
for i in range(64):
db2.get(f"q{i:02d}") # keys that are not stored
print("runs searched", db2.run_probes, "runs skipped", db2.bloom_skips)
# Output:
# 4 [4, 4, 4, 52]
# puts 64 entries written 172 per put 2.69
# runs searched 7 runs skipped 249#B+ Tree or LSM Tree
Neither structure wins everywhere. They move the work to different places. The B+ tree pays at write time to keep one tidy copy of the data. The LSM tree pays later and in bulk, and its reads must put together an answer from several places.
| Question | B+ tree | LSM tree |
|---|---|---|
| Point read | One block per level, a fixed, small number | Memtable, then up to R runs, cut down by Bloom filters |
| Range scan | Find the start, then read linked leaves in order | Merge the memtable and all runs in key order |
| How a write lands | Random read-modify-write of a leaf block | Log append, then memory, then a bulk sequential flush |
| Extra write cost | Page splits, plus the log | Compaction rewrites each entry several times |
| Space | Blocks kept half to fully full | Old versions and tombstones until compaction |
| Delete | Remove the key, merge blocks if too empty | Write a tombstone, clean up in compaction |
| Fits best | Read-heavy work, many range queries, steady latency | Write-heavy work and bulk ingest |
For example, SQLite and PostgreSQL index with B-tree family structures, while RocksDB and LevelDB are built on LSM trees. These are the well-known cases, and the choice is a trade-off, not a law. LSM stores add Bloom filters and caches to narrow their read gap, and B+ tree databases add buffering to narrow their write gap.
The table also lists what to ask about a workload. How many reads per write? Are there range scans? Do writes arrive in bulk? Is steady response time worth more than peak speed? Compaction can make an LSM tree's speed uneven, which is the usual worry.
#When Not to Use These
dict gives O(1) average lookups. A sorted list with bisect gives O(log n) lookups in sorted order, and an insert costs O(n) because of shifting, which is fine for thousands of items.A hash index is faster than a B+ tree for exact-match lookups, but it cannot answer range queries or "next key after this one". If a query never needs order, a hash index is often the right choice.
sorted uses Timsort, which finds sorted runs in the input and merges them. That is the compaction idea in memory: merge sorted runs instead of re-sorting the whole thing.#Common Mistakes
#Try It: Five Problems
tests line lists the inputs that matter: empty input, exact powers, tombstones that hide older values, and empty ranges. Problem 1 has a float trap, problem 3 has a search-order trap, and problem 5 merges several sources and keeps the newest value of each key.Tests · Expected output, line by line. Line 1: (0, 0) (1, 1) (1, 1) (2, 2) (3, 3), which covers empty input, one key, an exact full page, one key over, and the float trap at 125 keys with fanout 5. Line 2: True False [1, 2, 5, 7, 8, 9]. Line 3: 512 False True, after deleting every even key from 1024. Line 4: (None, 0) (2, 1) (3, 2) (None, 2), where the memtable tombstone hides both older values of b. Line 5: ([('a', 2), ('b', 5), ('c', '<deleted>'), ('d', 4)], 3). Line 6: ([('a', 2), ('b', 5), ('d', 4)], 3), with the tombstone dropped. Line 7: ([('x', 1)], 0), where one run is empty. Line 8: ([('a', 2), ('c', 3), ('d', 6), ('e', 8)], 7), where b is hidden and f is out of range. Line 9: ([], 0), an empty range.
#Recap
Disks hand out blocks, and sequential access beats random access, so a disk structure is judged by block reads. A tree whose nodes fill a block is wide and shallow: n keys need O(log_B n) reads. A B+ tree has linked leaves, splits full blocks so all leaves stay at one depth, and answers a range query in O(log_B n + k / B) reads.
A skip list builds express lanes with coin flips, so search and insert cost O(log n) in expectation and space O(n), as long as the flips are independent of the keys.
A write-ahead log makes memory-first structures safe: log first, then apply, then replay after a crash. An LSM tree turns writes into appends: a memtable flushes into immutable sorted runs, reads check newest to oldest, tombstones stand for deletes, Bloom filters skip runs, and compaction merges runs at the price of write amplification.
A B+ tree has 200 entries per block and holds 40,000 keys in its leaves, so the leaves take 200 blocks. How many levels does it have?
Key Takeaways
- Disk cost is counted in block reads, and sequential access beats random access, so wide shallow trees win
- A B+ tree with fan-out B finds a key in O(log_B n) reads, splits full blocks to stay at least half full, and scans ranges through linked leaves
- A skip list gets O(log n) expected time and O(n) expected space from independent coin flips, so sorted input does not hurt it
- A write-ahead log means log first, then apply, and a checksum lets replay stop at a half-written record
- An LSM tree trades read cost for write speed: memtable, immutable sorted runs, newest-first lookups, tombstones, Bloom filters and compaction
- Pick a B+ tree for read-heavy and range-heavy work, an LSM tree for write-heavy work, and neither when everything fits in memory