A memtable is a sorted map, plus one problem

The in-memory half of the engine is mostly a BTreeMap. The interesting part is what happens when you ask it for a key it does not have.

Writes cannot go straight to disk in sorted order — that would mean rewriting a file on every insert. So they go into memory first, into a structure that keeps them sorted, and get written out in bulk later. That structure is the memtable.

In Rust it is a BTreeMap<String, Option<String>> and roughly free. Sorted iteration comes with the type, which matters enormously later: flushing to disk becomes a linear walk instead of a sort.

The Option is doing real work

The value is Option<String>, not String. None is a tombstone — the same idea as the log, held in memory. A delete is not a removal from the map, it is an insert of None.

Which forces a question: what does get return? The obvious answer is Option<String>, and the obvious answer is wrong.

// Found means stop searching, Deleted means stop searching,
// NotFound means an older layer might still have it.
// Collapsing them into a plain Option would resurrect deleted keys.
pub enum Lookup {
    Found(String),
    Deleted,
    NotFound,
}

There are three outcomes, not two. Found — here is the value, stop looking. Deleted — I have a tombstone for this key, stop looking, the answer is no. NotFound — I have never heard of this key, keep looking in older layers.

Squash Deleted and NotFound into a single None and the read path cannot tell "this was deleted" from "this isn't here", so it falls through to the older file, finds the pre-delete value, and returns data the user deleted. The enum is not ceremony. It is the bug, made unrepresentable.

Knowing when to stop

The memtable tracks its own size in bytes and answers is_full() against a threshold. That is the trigger for a flush — the moment the in-memory half hands a batch of sorted data to the on-disk half. Which needs an on-disk half to exist first.