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

Why a single GET might touch many files

In a plain hash-table-backed store, a read is one lookup. In an LSM tree, a key's most recent value could be sitting in the memtable, in the newest flushed SSTable, in an SSTable flushed an hour ago, or several compaction levels deep — because writes are never updated in place, "the current value of key X" really means "the newest value of X across every layer that might contain it." This is read amplification: the cost LSM trees pay at read time in exchange for extremely cheap, append-only writes.

The layering order: newest wins, first match stops

The read path always searches from newest data to oldest:

1. Memtable — the current in-memory generation, always checked first since it holds the most recent writes.
2. L0 SSTables, newest first — L0 (level zero) files come directly from memtable flushes, so they can overlap in key range with each other (unlike deeper levels, which are compacted into non-overlapping runs). Because they can overlap, you must check them in strict recency order — the newest L0 file that contains the key wins, not just any L0 file that happens to contain it.
3. Deeper levels (L1, L2, ...) — compaction (a later chapter) merges L0 files down into non-overlapping, sorted runs at each level, which is what lets a lookup at L1+ binary-search a single file's index instead of checking every file in that level.

The moment any layer produces a match — value or tombstone — the search stops. That's the essential rule: don't keep looking past the first layer that has an answer, because that answer is by definition newer than anything in the layers below it.

Tombstones shadow, they don't just delete

A tombstone found in a newer layer must stop the search even though it carries no "real" value — that's the entire point of a tombstone as a data structure. If layer 2 (older) still has a=11 on disk, but layer 0 (newer, the memtable) recorded a as deleted, the correct answer is "deleted," not "fall through and find the stale value underneath." Get this wrong (e.g., by treating a tombstone as "absent, keep looking") and deletes silently fail to take effect whenever an older SSTable still holds the value — a real and dangerous class of bug in LSM implementations.

Tombstones are also why an LSM tree can't reclaim disk space the instant something is deleted: the tombstone itself has to persist (and shadow older versions) until compaction eventually rewrites the layers below it and can safely drop both the tombstone and the value it was shadowing. Until that happens, "deleted" is itself just another entry taking up space, layered on top like everything else.

Reasoning about correctness here

Two invariants make this whole scheme sound:

• Recency ordering is total — every layer has an unambiguous position in "newest to oldest," so "first match wins" is well-defined. (In your real engine, this ordering comes from generation/sequence numbers assigned at write time, not literally the order layers happen to be listed in.)
• A key's true current value is exactly the value in the newest layer that mentions it at all — whether that's a normal value or a tombstone. Older layers mentioning the same key are stale by construction and must never override a newer layer's answer.

Edge cases

• A key present in no layer at all is NOT_FOUND — distinct from a tombstone hit, which is DELETED. Don't conflate "never written" with "written then deleted."
• A key that appears in multiple layers: only the first (newest) match matters — don't merge or compare across layers, and don't accidentally scan further "just to check."
• Layer names in the output exist purely so you (and tests) can verify which layer answered a query — a good debugging habit that mirrors how real engines expose read statistics (e.g., "resolved from L0 file #3") for performance tuning.