DSA Storage Indexes
B-Trees & LSM-Trees
The query hits a 4 KB page, not a CPU register. A binary tree of height 40 is forty random I/Os. Raise so one page holds hundreds of separators and height collapses.
B-trees optimize with wide balanced pages (). buffer and compact when ingest dominates.
Decision journey
Cost model = pages
Not pointer hops in RAM.
Fit keys/children in one block.
B-tree vs LSM
Update-in-place pages vs flush/compact.
Measure amplification
Read, write, space, latency tails.
What actually happens
Naive idea: store a binary BST on disk. Breaks: each compare may be a page fault; height log₂ n is brutal for I/O.
Better idea: pack many keys per page. Height ≈ log_fanout(n). Splits/merges keep occupancy so every leaf sits at the same depth.
The improved design still fails if page size/fanout ignore the device, if concurrency/recovery are ignored, or if a write-heavy ingest workload needed LSM-style sequentialization instead.
Invariant
All leaves share the same depth. Non-root nodes obey occupancy bounds for degree t. Separators partition child key ranges. Correctness also includes durability and concurrency protocols in real engines.
How to choose B-tree vs LSM
1. Predictable point/range reads? B-tree / B+ tree families shine.
2. Sustained random ingest? LSM often wins write amp trade-offs.
3. Always measure? Amplification and p99 latency beat labels.
Quantitative check
n=10⁹ keys, fanout ≈ 200: height ≈ log₂₀₀(10⁹) ≈ 4 page reads on a cold cache. A binary tree would need ~30 random I/Os for the same search.
B-tree idea
wide + height-balanced
Many separators per page reduce expensive page visits along a root-to-leaf path.
LSM idea
buffer + sort + merge
Turn foreground random updates into memory writes and sequential immutable runs.
Shared requirement
durable ordering metadata
Recovery, versions, page/run publication, and concurrency are part of correctness.
Interactive write-path comparison
Step through a B-tree leaf split and an LSM WAL-to-compaction lifecycle. The visualizations use tiny pages and runs so every invariant is visible; production structures use much larger blocks and implementation-specific policies.
Storage-index lifecycle laboratory
Page splitting versus buffered merging
Follow the write path that each family optimizes. The diagrams show logical pages/runs, not a vendor-specific file format.
Start with a valid page-oriented B-tree
Step 1 / 5
root page
leaf 1
leaf 2
leaf 3
Observable result
height = 1 edge · 4 pages shown
B-tree invariants, stated precisely
Textbooks define “order” inconsistently, so the rules below use minimum degree t. A node can hold at most 2t−1 keys and at most 2t children. The root receives special lower-bound rules so a small tree remains valid.
Sorted node keys
k₀ < k₁ < …; separators partition the key ranges owned by the children.
Occupancy
With minimum degree t, each non-root node has t−1…2t−1 keys; the root is the documented exception.
Child count
An internal node with q keys has q + 1 children, each responsible for one separator interval.
Uniform leaf depth
Every root-to-leaf path has the same length, so no key inherits a degenerate chain.
Why page width changes the cost model
A node is sized around a storage or cache page. Roughly, internal fan-out is determined by how many separator-plus-child-pointer pairs fit after headers and metadata:
fan-out ≈ ⌊(page bytes − header) / (separator bytes + child pointer bytes)⌋
Prefix compression, variable-size keys, fence keys, checksums, sibling links, and fill-factor policy all change the actual number.
Page visits
Θ(log_f N)
f is effective fan-out; a large f makes height small.
Inside one page
binary search or tuned scan
CPU comparisons matter after the page is resident.
Cache effect
root often stays hot
Not every logical level necessarily causes physical I/O.
Search in matching Python and Java
This classic B-tree search returns whether a key exists. A lower-bound search finds either the equal separator or the child interval.
Python
from bisect import bisect_left
class BTreeNode:
def __init__(self, keys, children=()):
self.keys = list(keys)
self.children = list(children)
@property
def leaf(self):
return not self.children
def contains(node, target):
current = node
while True:
i = bisect_left(current.keys, target)
if i < len(current.keys) and current.keys[i] == target:
return True
if current.leaf:
return False
current = current.children[i]Java
import java.util.List;
final class BTreeSearch {
static final class Node {
final int[] keys;
final List<Node> children;
Node(int[] keys, List<Node> children) {
this.keys = keys;
this.children = children;
}
boolean isLeaf() { return children.isEmpty(); }
}
static int lowerBound(int[] keys, int target) {
int low = 0, high = keys.length;
while (low < high) {
int mid = low + (high - low) / 2;
if (keys[mid] < target) low = mid + 1;
else high = mid;
}
return low;
}
static boolean contains(Node root, int target) {
Node current = root;
while (true) {
int i = lowerBound(current.keys, target);
if (i < current.keys.length && current.keys[i] == target) return true;
if (current.isLeaf()) return false;
current = current.children.get(i);
}
}
}Insertion and deletion repair occupancy
Insert by splitting full nodes
- 1Search for the target leaf while keeping the path or splitting full children on descent.
- 2Insert the key in sorted order inside a non-full leaf.
- 3On a split, promote a median separator and create two legal children.
- 4If the root splits, create a new root; height increases by exactly one.
Delete by strengthening the next child
- 1Before descending, ensure the chosen child has at least t keys when possible.
- 2Borrow from a sufficiently large sibling through the parent, or merge siblings with a separator.
- 3For an internal key, use a predecessor/successor from a large child or merge before continuing.
- 4If the root becomes empty with one child, promote that child; height decreases by one.
Node search is logarithmic in the number of separators, but moving keys within a page is proportional to page occupancy. In external-memory analysis, the dominant metric is usually Θ(height) page transfers; CPU and write-latency details still matter in memory.
The LSM write path
WAL
Append recovery information according to the durability/sync contract.
Memtable
Apply the newest version to an ordered mutable in-memory structure.
Flush
Write an immutable sorted run and publish it through durable metadata.
Read
Reconcile newest-to-oldest versions across memory and candidate runs.
Compact
Merge runs, discard obsolete versions when safe, and enforce level policy.
WAL does not mean every write calls fsync
Engines define sync, group-commit, and acknowledgement policies. The durability boundary must be explicit; merely calling a file write API may leave bytes in volatile caches.
Immutable does not mean never rewritten
An SSTable is not updated in place, but compaction creates replacement files and later retires old ones. LSM storage is write-heavy in the background by design.
Point lookup must distinguish missing, value, and tombstone
A tombstone is a newer deletion that must stop older values from resurfacing. Bloom filters may skip runs that definitely lack a key, but a positive still requires index/block lookup and sequence-number reconciliation.
Python
from dataclasses import dataclass
from enum import Enum, auto
class Kind(Enum):
MISSING = auto()
TOMBSTONE = auto()
VALUE = auto()
@dataclass(frozen=True)
class Lookup:
kind: Kind
value: object = None
MISSING = Lookup(Kind.MISSING)
def lsm_get(key, memtable, runs_newest_first):
result = memtable.get(key, MISSING)
if result.kind is not Kind.MISSING:
return result
for run in runs_newest_first:
if not run.bloom.might_contain(key):
continue
result = run.lookup(key)
if result.kind is not Kind.MISSING:
return result
return MISSINGJava
import java.util.List;
import java.util.Map;
final class LsmLookup {
enum Kind { MISSING, TOMBSTONE, VALUE }
record Lookup<V>(Kind kind, V value) {
static <V> Lookup<V> missing() {
return new Lookup<>(Kind.MISSING, null);
}
}
interface Run<K, V> {
boolean mightContain(K key);
Lookup<V> lookup(K key);
}
static <K, V> Lookup<V> get(
K key, Map<K, Lookup<V>> memtable, List<Run<K, V>> newestFirst) {
Lookup<V> memory = memtable.get(key);
if (memory != null) return memory;
for (Run<K, V> run : newestFirst) {
if (!run.mightContain(key)) continue;
Lookup<V> result = run.lookup(key);
if (result.kind() != Kind.MISSING) return result;
}
return Lookup.missing();
}
}Real engines also apply snapshot sequence numbers, range tombstones, merge operands, checksums, and visibility rules. A plain null return cannot encode every state safely.
Compaction policy moves the trade-offs
Leveled
Keep bounded, mostly non-overlapping ranges per lower level. Point reads improve, but data may be rewritten across several levels.
Size-tiered
Merge runs of similar size. Foreground writes are cheap and rewrite frequency can fall, while reads and temporary space may increase.
Hybrid / universal
Choose candidates by size, overlap, age, and workload. Names and exact guarantees are implementation-specific.
B-tree versus LSM: amplification ledger
| Dimension | B-tree family | LSM-tree family |
|---|---|---|
| Primary write shape | Update one root-to-leaf path; may split/merge pages | Append WAL, update memtable, later flush and compact runs |
| Point read | One page path, often helped by cache | Newest mutable state plus candidate runs; Bloom filters skip definite misses |
| Range scan | Excellent in B+ trees through linked leaves | Merge sorted iterators while reconciling versions and tombstones |
| Write amplification | Page writes, splits, logging, and engine-specific maintenance | Compaction may rewrite the same logical bytes multiple times |
| Read amplification | Usually bounded by tree height | May consult several runs/levels, mitigated by indexes, filters, and cache |
| Space amplification | Free space inside pages and retained versions | Multiple runs, obsolete versions, tombstones, and compaction headroom |
| Typical strength | Predictable reads, ordered updates, transactional indexes | High ingest throughput and sequentialized background work |
Failure and concurrency boundaries
Torn or partial publication
New pages/runs and their parent or manifest metadata must become visible in a recoverable order. Checksums detect corruption; logs or copy-on-write protocols recover structure.
Concurrent readers during structural change
Latches, optimistic validation, versioned pages, or immutable snapshots must ensure a split/merge/compaction does not expose a half-published search path.
Cache and memory pressure
A larger memtable or page cache can improve throughput until flush bursts, garbage collection, eviction, or recovery time violates the latency budget.
Background debt
If compaction or page maintenance cannot keep up, pending work grows. Monitor level sizes, overlap, stalls, write amplification, cache hit rate, and tail latency, not only average throughput.
Decision rule
Favor a B-tree family when predictable point/range reads, page-oriented ordered updates, and mature transactional page machinery dominate. Favor an LSM family when sustained ingest and sequentialized writes justify background compaction and more complex reads. Then choose page size, fan-out, memtable size, filters, cache, compaction, durability, and retention from measured workload constraints, not labels alone.
Short takeaway
B-trees raise fanout to match disk pages so lookups pay a handful of I/Os. LSM trees buffer and compact when write throughput dominates; compare amplification, not slogans.
Exercises
- Why does fanout ≈ page_size / key_size matter more than “binary vs multiway” as a slogan?
- n=10⁹, fanout 250. Estimate B-tree height. Compare to log₂(10⁹).
- Name one workload where LSM write amplification is acceptable and one where a B-tree’s update-in-place path is preferable.
Primary sources
- Bayer & McCreight (1972): Organization and maintenance of large ordered indexes (B-trees).
- O'Neil et al.: The log-structured merge-tree (LSM-tree).
- Database engine literature on B+ trees, buffer pools, and compaction policies.