Deep Dive: Read Amplification

B-Tree Read Amplification (The Winner)

Because B-Trees maintain a sorted, indexed structure at all times, finding a specific record is deterministic and efficient:

1. Read the root page (likely cached in the buffer pool in RAM).
2. Read one internal node page.
3. Read one leaf page containing the actual row data.

For a table with 1 billion rows, a B-Tree with 4 KB pages and 8-byte keys needs only 3–4 page reads to locate any record. The data is always exactly where the index says it is. Read Amplification ≈ 1 for point queries.

Range queries are even better: because data is sorted within and across pages, a range scan reads contiguous pages sequentially — the fastest possible I/O pattern.

LSM Tree Read Amplification (The Challenge)

LSM Trees fragment data across multiple files at multiple levels. To find the current value of a record, the engine must check every location where a newer version might exist:

Read Path for key "user_id=123":
  1. Check MemTable (RAM) — not found
  2. Check L0 SSTable file 1 — not found
  3. Check L0 SSTable file 2 — not found
  4. Check L0 SSTable file 3 — not found
  5. Check L1 SSTable — not found
  6. Check L2 SSTable — FOUND (value from 3 days ago)

  Total: 6 file lookups for 1 logical read

Without mitigation, Read Amplification in an LSM Tree can reach 10–50x for point queries, making it completely impractical for read-heavy workloads.

The Band-Aid: Bloom Filters

To make LSM reads competitive, every production LSM implementation uses Bloom Filters — a probabilistic data structure that answers the question: "Does this SSTable file definitely NOT contain this key?"

A Bloom Filter for an SSTable is built when the SSTable is written. It hashes every key in the file and sets bits in a compact bit array. When a read arrives:

1. Hash the target key.
2. Check the Bloom Filter bit array.
3. If the bits say "definitely not here" → skip this file entirely (no disk read).
4. If the bits say "might be here" → read the file (may be a false positive, but never a false negative).

A well-tuned Bloom Filter (10 bits per key) achieves a false positive rate of ~1%. This means 99% of unnecessary SSTable reads are eliminated. Read Amplification drops from 10–50x to roughly 2–3x.

The cost: Bloom Filters consume memory. For a database with 1 billion keys at 10 bits per key, the Bloom Filters require ~1.25 GB of RAM. This is the Space Amplification trade-off in action — you spend memory to buy back read performance.

Key Point: The effectiveness of Bloom Filters degrades for range queries. A Bloom Filter can tell you whether a specific key exists in a file, but it cannot tell you whether any key in a range exists. For range scans, LSM Trees still suffer high read amplification, which is why databases like Cassandra are notoriously poor at range queries compared to PostgreSQL.