How LSM-tree databases read data fast

1 The read problem in LSM trees

Quick recall from Session 10: an LSM tree (Log-Structured Merge tree) never updates data in place. Instead it:

• Buffers new writes in memory in a sorted structure called the MemTable.
• When the MemTable fills up, it gets flushed to disk as an immutable, sorted file called an SSTable (Sorted String Table).
• Over time you accumulate many SSTables, each a frozen snapshot of writes from a different point in time.

This append-only design is what makes writes so fast (we covered that last session). But it creates a brand-new headache on the read side. When someone asks for the value of a key, where is it?

Why a key could be anywhere

A single key — say user:42 — might live in several places at once, because every write created a new copy somewhere newer:

The naive read: check everything

The simplest possible read works like this:

If we check newest-to-oldest and stop the moment we find the key, that's correct — but it can be agonisingly slow. The truly painful case is a key that doesn't exist: to be sure, we'd have to read every SSTable completely before giving up.

The three tools we'll build

2 The read path & tombstones

The read path is the exact ordered procedure the database follows to answer "give me the value for key K." The golden rule is newest wins: because newer data was written later, it overrides anything older.

The order of search

We always look in the MemTable first because it holds the very latest writes (they haven't even been flushed yet). If the key isn't there, we move to disk and check SSTables from newest to oldest. The first place we find the key has the current value — we return it immediately and never look at older copies.

Deletes are tricky — meet the tombstone

Here's a puzzle. SSTables are immutable — once written, you can never go back and erase a key from them. So how do you delete something? You can't reach into an old, frozen file and rub it out.

The trick: a delete is just another write. To delete key K, the database writes a special marker called a tombstone — a record that says "K has been deleted" instead of a real value. Because it's the newest write for K, the read path finds it first and reports the key as gone, even though older SSTables still contain the old value.

Two naive deletion ideas (and why they fail)

Before we land on tombstones, it's worth seeing why the obvious approaches don't work:

TOMBSTONE = "PZpaIBk8rbaIQVoUqGD2NS04qD3gONn0QH1Cm2DKBkoktwGuEt"
// it is practically impossible for your data to contain this exact string by chance

With a tombstone constant, delete is implemented as a set, and get simply treats the tombstone as "not found":

void set(key, value) {
    ...
}

void delete(key) {
    set(key, TOMBSTONE)          // a delete is just a write
}

string _get(key) {
    // check memtable
    // check sstables
    // ...
}

string get(key) {
    value = _get(key)
    if (value == TOMBSTONE) {
        raise KeyNotFoundError!
    }
    return value
}

The read path in pseudocode

function read(key):
    # 1. Check the in-memory MemTable first (newest data)
    result = memtable.get(key)
    if result is not NONE:
        return unwrap(result)   # could be a value OR a tombstone

    # 2. Walk SSTables from newest to oldest
    for sstable in sstables_newest_to_oldest:
        # (bloom filter + sparse index go here — Topics 3 & 4)
        result = sstable.get(key)
        if result is not NONE:
            return unwrap(result)

    return NOT_FOUND          # looked everywhere; key truly absent

function unwrap(result):
    if result.is_tombstone:
        return NOT_FOUND      # a delete marker means "gone"
    return result.value

How compaction helps reads

Recall compaction from Session 10: a background process that merges several SSTables into one, keeping only the newest version of each key and physically dropping tombstones (and the dead values they shadow). It runs while writes keep flowing, so it never blocks the user.

Compaction is the read side's best friend for three reasons:

• Fewer files to search. Merging 10 SSTables into 1 means a read checks 1 file instead of 10.
• Less duplication. Old, overwritten versions of a key are thrown away, so reads don't waste time stepping over stale copies.
• Tombstones eventually disappear. Once a tombstone has out-lived every older copy of its key, compaction drops it entirely, reclaiming disk space.

3 The cost of disk reads & why we need an index

Binary search is wonderful… in theory

Binary search runs in O(log n), which is ultra-fast compared to linear search's O(n). Consider a database with 1 trillion entries:

That makes binary search about 25 billion times faster than linear search here. So why not just binary-search the SSTable and call it a day?

How big do SSTables get?

SSTables grow as they're compacted up the levels. With a typical WAL size of 100 MB, each level roughly doubles (because each SSTable is compacted from two SSTables of the level below):

Attempt 1: a full index (and why it's too big)

The simplest index: keep a hashmap of {key: offset} in RAM for each SSTable. Given a key, we don't binary-search the SSTable at all — we look it up in the index, which hands us the exact byte offset to read. Reads become O(1) per SSTable — the 30× speedup.

The problem is memory. A full index has one entry per SSTable entry:

4 Sparse index

Topic 2 told us which SSTables to search and in what order. But there's a second problem: once we've picked an SSTable, how do we find a key inside it without reading the whole file? SSTables can be huge — gigabytes. We need a way to jump close to the key.

The crucial advantage: SSTables are sorted

Remember the "Sorted" in Sorted String Table. Inside an SSTable, the keys are stored in sorted order. That single fact is what makes everything fast, because sorted data lets us use binary search (repeatedly halving the search range) instead of reading linearly. But binary search over data on disk still means many separate disk seeks. The sparse index cuts that down further.

Dense vs sparse: why "sparse"?

A dense index would store the exact disk position (the offset — the byte location in the file) of every single key. That's a lot of index — potentially as big as the data itself, and too big to keep in memory.

A sparse index stores the offset of only some keys — say, the first key of every disk block (a fixed-size chunk of the file, e.g. 4 KB read in one shot). It's small enough to live entirely in memory.

How a lookup works with a sparse index

Suppose an SSTable's sparse index (held in memory) looks like this — only the first key of each block, with its byte offset:

Just how much smaller is a sparse index?

A sparse index is built for each SSTable, kept in RAM, and constructed once when the SSTable is created. The key insight: because data is always read/written in fixed-size blocks, we only need to index the first key of each block, not every key. Reusing the 100 GB SSTable from the previous section:

The picture

Sparse index lookup in code

# Python
from bisect import bisect_right

# The sparse index: sorted (first_key_of_block, byte_offset) pairs, in RAM.
sparse_index = [("apple", 0), ("cherry", 4096), ("mango", 8192), ("peach", 12288)]

# Stand-in for a real file: each block is the run of (key, value) it holds.
blocks = {
    0:     [("apple", "A"), ("banana", "B")],
    4096:  [("cherry", "C"), ("lemon", "L"), ("lime", "Li")],
    8192:  [("mango", "M"), ("orange", "O")],
    12288: [("peach", "P")],
}

def disk_read(offset):       # the ONE disk read
    return blocks[offset]

def sstable_get(key):
    keys = [k for (k, _) in sparse_index]
    # binary search: largest indexed key <= key
    i = bisect_right(keys, key) - 1
    if i < 0:
        return None           # key sorts before the very first block

    _, offset = sparse_index[i]
    block = disk_read(offset)   # one disk read of the candidate block
    for (k, v) in block:        # short in-memory linear scan
        if k == key:
            return v
    return None               # not in this SSTable


# --- tiny demo ---
print(sstable_get("lemon"))   # "L"   (cherry block @4096, then scan)
print(sstable_get("grape"))   # None  (apple block @0 scanned, absent)

// C++
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#include <optional>
#include <iostream>

using Entry = std::pair<std::string, std::string>;   // (key, value)

// Sparse index: sorted (first_key_of_block, byte_offset), in RAM.
std::vector<std::pair<std::string, long>> sparse_index = {
    {"apple", 0}, {"cherry", 4096}, {"mango", 8192}, {"peach", 12288}
};

// Stand-in for a file: each block is the run of entries it holds.
std::map<long, std::vector<Entry>> blocks = {
    {0,     {{"apple", "A"}, {"banana", "B"}}},
    {4096,  {{"cherry", "C"}, {"lemon", "L"}, {"lime", "Li"}}},
    {8192,  {{"mango", "M"}, {"orange", "O"}}},
    {12288, {{"peach", "P"}}}
};

std::optional<std::string> sstable_get(const std::string& key) {
    // binary search: largest indexed key <= key
    auto it = std::upper_bound(
        sparse_index.begin(), sparse_index.end(), key,
        [](const std::string& k, const auto& e){ return k < e.first; });
    if (it == sparse_index.begin()) return std::nullopt;  // before first block
    --it;

    const auto& block = blocks[it->second];   // one disk read of candidate block
    for (const auto& [k, v] : block)        // short in-memory scan
        if (k == key) return v;
    return std::nullopt;                  // not in this SSTable
}

int main() {
    auto a = sstable_get("lemon");
    auto b = sstable_get("grape");
    std::cout << (a ? *a : "NONE") << "\n";   // L
    std::cout << (b ? *b : "NONE") << "\n";   // NONE
    return 0;
}

// Java
import java.util.*;

class SparseIndexLookup {
    record Entry(String key, String value) {}

    // Sparse index: sorted first-key-of-block -> byte offset, in RAM.
    static final String[] indexKeys   = {"apple", "cherry", "mango", "peach"};
    static final long[]   indexOffsets = {0, 4096, 8192, 12288};

    // Stand-in for a file: each block is the run of entries it holds.
    static final Map<Long, List<Entry>> blocks = Map.of(
        0L,     List.of(new Entry("apple", "A"),  new Entry("banana", "B")),
        4096L,  List.of(new Entry("cherry", "C"), new Entry("lemon", "L"), new Entry("lime", "Li")),
        8192L,  List.of(new Entry("mango", "M"),  new Entry("orange", "O")),
        12288L, List.of(new Entry("peach", "P")));

    static String sstableGet(String key) {
        // binary search: largest indexed key <= key
        int i = Arrays.binarySearch(indexKeys, key);
        if (i < 0) i = -(i + 1) - 1;   // insertion point - 1
        if (i < 0) return null;         // before first block

        List<Entry> block = blocks.get(indexOffsets[i]);  // one disk read
        for (Entry e : block)              // short in-memory scan
            if (e.key().equals(key)) return e.value();
        return null;                      // not in this SSTable
    }

    public static void main(String[] args) {
        System.out.println(sstableGet("lemon"));  // L
        System.out.println(sstableGet("grape"));  // null
    }
}

5 Bloom filters

The sparse index made searching inside one SSTable fast. But there's still the problem from Topic 1: a key might be in any of the SSTables, and looking for a non-existent key means touching them all. A bloom filter fixes this. It's a tiny, fast, probabilistic structure that answers one question per SSTable: "Could this key be in here?" If the answer is "no," we skip that SSTable entirely — no disk read at all.

What kind of structure is a bloom filter?

A bloom filter is a probabilistic data structure. It supports only two operations — insert and containment check. It does not support reads, updates, deletes, or iteration. And its containment check can "lie" — but only in one direction:

How it's built: a bit array + k hash functions

A bloom filter is just two things:

• A bit array of m bits, all starting at 0.
• A set of k independent hash functions. (A hash function turns any key into a number; here we use the result, modulo m, as an index into the bit array.)

To add a key (done when the SSTable is written): run the key through all k hash functions to get k positions, and set those bits to 1.

To test a key (done at read time): hash it the same way to get k positions. If all of those bits are 1 → answer "maybe." If any bit is 0 → answer "definitely not" (because if the key had been added, that bit would have been set).

index:  0 1 2 3 4 5 6 7 8 9
bits:   0 0 0 0 0 0 0 0 0 0

index:  0 1 2 3 4 5 6 7 8 9
bits:   0 0 1 0 0 0 0 1 0 0

index:  0 1 2 3 4 5 6 7 8 9
bits:   0 0 1 0 1 0 0 1 0 0

Bloom filter in code

# Python
class BloomFilter:
    def __init__(self, m, k):
        self.m = m                  # number of bits
        self.k = k                  # number of hash functions
        self.bits = [0] * m       # bit array, all zero

    def _positions(self, key):
        # derive k independent indices from one base hash
        h = hash(key)
        h1, h2 = h & 0xFFFFFFFF, (h >> 32) & 0xFFFFFFFF
        for i in range(self.k):
            yield (h1 + i * h2) % self.m   # double hashing

    def add(self, key):
        for pos in self._positions(key):
            self.bits[pos] = 1

    def might_contain(self, key):
        for pos in self._positions(key):
            if self.bits[pos] == 0:
                return False      # a 0 bit => definitely NOT present
        return True               # all 1 => possibly present (maybe false positive)


# --- tiny demo ---
bf = BloomFilter(m=100, k=3)
for word in ("apple", "mango", "cherry"):
    bf.add(word)

print(bf.might_contain("apple"))   # True  (was added)
print(bf.might_contain("grape"))   # False or True; if False it is DEFINITELY absent
# A "False" is always trustworthy: no false negatives.
# A "True" may be a false positive -- confirm with the real lookup.

# Sizing: for n keys at false-positive rate p,
#   m = ceil(-n * ln(p) / (ln 2)^2)   bits
#   k = round((m / n) * ln 2)         hashes
# e.g. p = 1%  ->  ~10 bits per key, k = 7.

// C++
#include <vector>
#include <string>
#include <functional>
#include <iostream>

class BloomFilter {
    size_t m_, k_;
    std::vector<bool> bits_;          // m bits, all false

    // derive k indices from one base hash (double hashing)
    template <class F>
    void positions(const std::string& key, F fn) const {
        size_t h  = std::hash<std::string>{}(key);
        size_t h1 = h & 0xFFFFFFFFu;
        size_t h2 = (h >> 32) & 0xFFFFFFFFu;
        if (h2 == 0) h2 = 1;
        for (size_t i = 0; i < k_; ++i) fn((h1 + i * h2) % m_);
    }

public:
    BloomFilter(size_t m, size_t k) : m_(m), k_(k), bits_(m, false) {}

    void add(const std::string& key) {
        positions(key, [&](size_t pos){ bits_[pos] = true; });
    }

    bool might_contain(const std::string& key) const {
        bool all_set = true;
        positions(key, [&](size_t pos){ if (!bits_[pos]) all_set = false; });
        return all_set;    // false => definitely absent; true => maybe present
    }
};

int main() {
    BloomFilter bf(100, 3);
    for (const std::string& w : {"apple", "mango", "cherry"}) bf.add(w);

    std::cout << bf.might_contain("apple") << "\n";  // 1  (was added)
    std::cout << bf.might_contain("grape") << "\n";  // 0 or 1; if 0 it is DEFINITELY absent
    // No false negatives: a "0" can be trusted. A "1" may be a false positive.

    // Sizing: for n keys at false-positive rate p,
    //   m = ceil(-n * ln(p) / (ln 2)^2)  bits
    //   k = round((m / n) * ln 2)        hashes   (p = 1% -> ~10 bits/key, k = 7)
    return 0;
}

// Java
import java.util.BitSet;

class BloomFilter {
    private final int m, k;
    private final BitSet bits;        // m bits, all clear

    BloomFilter(int m, int k) {
        this.m = m;
        this.k = k;
        this.bits = new BitSet(m);
    }

    // derive k indices from one base hash (double hashing)
    private int[] positions(String key) {
        long h  = key.hashCode() & 0xFFFFFFFFL;
        long h2 = (Long.rotateLeft(h, 17) | 1) & 0xFFFFFFFFL;
        int[] pos = new int[k];
        for (int i = 0; i < k; i++)
            pos[i] = (int) (((h + (long) i * h2) % m + m) % m);
        return pos;
    }

    void add(String key) {
        for (int pos : positions(key)) bits.set(pos);
    }

    boolean mightContain(String key) {
        for (int pos : positions(key))
            if (!bits.get(pos)) return false;   // a clear bit => definitely absent
        return true;                          // all set => maybe present
    }

    public static void main(String[] args) {
        BloomFilter bf = new BloomFilter(100, 3);
        for (String w : new String[]{"apple", "mango", "cherry"}) bf.add(w);

        System.out.println(bf.mightContain("apple")); // true  (was added)
        System.out.println(bf.mightContain("grape")); // false or true; if false, DEFINITELY absent
        // No false negatives: "false" is trustworthy. "true" may be a false positive.

        // Sizing: for n keys at false-positive rate p,
        //   m = ceil(-n * ln(p) / (ln 2)^2)  bits
        //   k = round((m / n) * ln 2)        hashes   (p = 1% -> ~10 bits/key, k = 7)
    }
}

Plugging it into set() and get()

Every write inserts the key into the bloom filter; every read first asks the bloom filter and bails out immediately on a "no":

void set(key, value) {
    bloom_filter.insert(key)
    // … proceed with the DB insertion
}

string get(key) {
    if (! bloom_filter.contains(key))
        raise KeyNotFound!       // guaranteed never inserted
    // if bloom filter says key found, the DB might or might not have the key
    // proceed with normal DB check
}

Plugging it into the read path

Now we can complete the read path from Topic 2. Each SSTable keeps its own small bloom filter in memory. Before doing any disk work on an SSTable, we ask its bloom filter:

    for sstable in sstables_newest_to_oldest:
        if not sstable.bloom.might_contain(key):
            continue              # skip — no disk read at all!
        result = sstable.get(key)    # uses the sparse index (Topic 3)
        if result is not NONE:
            return unwrap(result)

Tuning: false-positive rate

The chance of a false positive depends on three things: the number of bits m, the number of keys n stored, and the number of hash functions k. More bits per key → fewer collisions → fewer false positives. A common target is around 1%, which costs only about 10 bits per key — astonishingly cheap.

★ Putting it all together

You now understand how LSM-tree databases turn their fast-write design into fast reads too. Here's the one-paragraph story that connects all four topics:

The final structure & algorithm

Here is the complete picture of how a mature LSM tree handles a write and a read, pulling every piece together.

Quick self-check

📚 References & Further Reading

Class material

• 📄 Original class notes / handout (Google Doc) — open the shared class material for this session.
• Class handout: "[SST-2028] NoSQL Internals - LSM Tree + Bloom Filter + Sparse Index".

Papers, docs & deep dives

• 📄 Bloom, B. H. — "Space/time trade-offs in hash coding with allowable errors" (1970) — the original bloom filter paper.
• 📄 Bloom Filters by Example (interactive tutorial) — a visual, hands-on explainer of how bloom filters work.
• 📄 RocksDB — Bloom Filter docs — how a production LSM engine uses per-SSTable bloom filters to skip files.
• 📘 Designing Data-Intensive Applications (Kleppmann), Ch. 3 — SSTables, sparse indexes, and bloom filters in LSM storage.

Interactive tools & visualizations

• 🌳 LSM Tree Visualizer — watch writes, flushes, and compaction happen live (source on GitHub).
• 🧮 Bloom filter calculator (hur.st) — compute the optimal bit-array size m and number of hashes k for a target false-positive rate.
• 📐 Bloom filter — math & code (Brilliant.org) — the probability math behind false-positive rates.