B+ trees and log-structured merge trees

Prerequisites: Ordered keys, balanced trees, pages, and durable storage.

Learning objectives

• Trace a B+ tree point and range lookup.
• Explain LSM flushing and compaction.
• Compare read, write, and space amplification.

An index reduces the pages inspected to answer a predicate, but maintaining it consumes writes, memory, and storage. A B+ tree organizes ordered separators in internal pages and data entries or record references in leaves. All leaves have the same depth. Searching chooses a child interval at each internal page, then locates the key in a leaf. Linked leaves support a range scan after the initial descent.

Assume an internal page can direct a search to one hundred children and each leaf holds two hundred entries. A root above one hundred leaves can address about twenty thousand entries; another internal level raises that capacity by roughly a factor of one hundred. Actual fanout depends on page size, key size, pointers, and occupancy. These are page-level estimates, not exact capacity guarantees. A cached root also changes physical I/O without changing tree height.

Suppose a leaf holds keys [10,20,30,40] and insertion of 25 exceeds its allowed capacity. Splitting distributes entries across two leaves and inserts a separator into the parent. A full parent may split recursively. The implementation must preserve search invariants during concurrent access and recover after interruption. A logical one-row insertion can therefore modify several pages and log records. Random updates also create scattered page writes.

A log-structured merge tree first accumulates updates in an ordered memory structure, generally protected by a durability log. A flush writes an immutable sorted run. Reads may inspect memory and several runs, combining versions according to sequence order and honoring deletion markers called tombstones. Compaction merges runs and discards obsolete versions when safe. It converts scattered updates into larger sequential transfers, but those merges rewrite data.

Consider an old run containing (k,blue), then a newer run containing (k,green). Reading k must return green, not whichever run is consulted first accidentally. A newer tombstone means absent. Removing that tombstone before all older copies are covered can resurrect blue. Snapshot readers and replica policies can further restrict when old versions may be discarded.

Read amplification measures extra structures or bytes consulted; write amplification measures storage writes per logical write; space amplification measures extra retained storage. Bloom filters can avoid many absent-key run probes, with false positives but no false negatives under correct construction and use. They do not locate the value or replace ordering for range scans.

Neither index family wins for every workload. Measure key distribution, update rate, scan length, memory budget, device behavior, and compaction interference. A write-heavy workload can tolerate additional read work; a latency-sensitive range workload may value predictable traversal. Explain the mechanism behind the choice, then measure the actual implementation.

Practice problem

A database stores an old sorted run with a=1 and b=2. Its newer run contains a=3 and a tombstone for b, while memory contains c=4. State the visible mapping and explain the danger of deleting b’s tombstone alone. Then estimate the leaf-page count for one million entries at 200 entries per leaf and the approximate search path with internal fanout 100, assuming full pages. Identify two reasons measured disk reads may differ.

Worked solution

The visible mapping is a=3 and c=4; b is absent. Dropping only b’s tombstone while the older b=2 remains searchable resurrects deleted data. A safe compaction must account for all relevant older copies and any snapshot requirements. One million entries require about 5000 leaves at the stated occupancy. One intermediate internal level needs about 50 pages, so a root, one internal page, and one leaf form the search path. Cached upper levels can reduce disk reads, while partially occupied pages, overflow values, concurrent maintenance, or a different actual fanout can increase work. The estimate describes the simplified tree structure, not a latency guarantee.

Check your understanding

A B+ tree has cached upper levels and linked ordered leaves. To retrieve keys 100 through 199, which access pattern follows its structure?

• Scan every internal page because ordering exists only at the root.
• Hash each requested integer into an unrelated bucket.
• Descend to the first qualifying leaf, then scan ordered leaf entries until the upper bound.
• Run a full independent root-to-leaf lookup for every stored entry.

Explanation

One boundary search locates the start; leaf ordering supports sequential continuation.

An old LSM run contains k=blue; a newer run contains a tombstone for k. Why is deleting only the tombstone unsafe?

• It is safe whenever the old run is immutable.
• It can make blue visible again.
• It changes blue’s key hash.
• It causes a false negative in every Bloom filter.

Explanation

Immutability does not make the old value irrelevant. The tombstone must continue suppressing it until safe compaction or visibility rules remove the older version.

Primary reading

• Indexes and filters I: Carnegie Mellon University
• Indexes and filters II: Carnegie Mellon University

Open the study and save your work →