The Read Path: Memtable → L0 → L1 → ...

To read a key, the LSM engine searches multiple sources, newest first, returning the first hit:

1. Active memtable               (just written)
2. Immutable (sealed) memtables  (being flushed)
3. L0 SSTables (newest first)    (recent flushes)
4. L1 SSTables  (overlapping check via index)
5. L2 SSTables
...
N. Bottommost level

The first place a key is found wins. If the value is a tombstone (Ch 7), return "not found".

Why Newest First?

Because newer writes shadow older ones. A key may exist in three SSTables — the engine must return the version with the largest sequence number, which is always in the newest source.

Pruning by Key Range

Each SSTable's footer records its smallest and largest keys. Before touching the file, the engine checks: does smallest_key <= target <= largest_key? If not, skip the SSTable entirely. This prunes most files at most levels for any given lookup.

For L1+ (non-overlapping), key range pruning means at most ONE SSTable per level can possibly contain the key. With 7 levels, that's at most 7 SSTable touches.

Bloom Filters: The Final Defense

Even after key-range pruning, the engine may still need to peek inside an SSTable that could contain the key but doesn't. That costs one disk read. A bloom filter (Ch 4) is a tiny probabilistic data structure that says "definitely not present" or "maybe present." With a 1% false-positive rate, 99% of negative lookups are answered with zero disk reads.

Worst-Case Cost

Without bloom filters, a missing-key read costs:

• 1 memtable lookup
• N L0 SSTables × 1 disk read each (each L0 may contain the key)
• (L-1) deeper-level SSTables × 1 disk read each

With bloom filters most disk reads are eliminated. With everything cached, lookups are sub-millisecond.

Concurrency

Reads never need a write lock. Each SSTable is immutable; the memtable uses a concurrent skip list. The MANIFEST tracks the current "version" — a snapshot of which SSTables are live. A read pins a version at start, sees only those SSTables, and the version is unpinned on completion. Compactions create a new version and leave the old SSTables on disk until no read pins them.

This is essentially MVCC for files: old versions stay live until no reader needs them.