Step 01 — Range Tombstones

Goal

Implement a single record that logically deletes every key in [start, end) without writing one Delete per key, and prove the priority rules with two adversarial tests.

What to Build

  • A RangeTomb { start_key, end_key } value type with a covers(key) predicate (key >= start && key < end).
  • An Sst carries a Vec<RangeTomb> alongside its Vec<Entry>.
  • LsmTreeAdvanced::get walks SSTs newest → oldest, accumulating active tombstones into a local vector as it goes.

The Two Rules That Matter

  1. A range tombstone hides keys older than it — i.e. in SSTs that appear later in the newest-first walk.
  2. A range tombstone does not hide keys newer than it — i.e. in SSTs that appear earlier in the walk.

The Two Tests That Pin Them

  • range_tomb_hides_older_put: newer SST has tomb [k0, k5), older SST has Put(k3, "hello"). get("k3") must return None.
  • range_tomb_respects_newer_put: newest SST has Put(k3, "fresh"), middle SST has tomb [k0, k5), oldest SST has Put(k3, "stale"). get("k3") must return Some("fresh").

Subtlety: Bloom Misses

When the bloom of an SST says "key not here", you cannot return early from get. The skipped SST might contribute a range tombstone that would shadow something below. So a bloom miss continues the walk; only a range-tombstone match early-exits with None.

Done When

  • Both tests above pass in all three languages.
  • The range_tombstones are present in dump_state per Section 4 of docs/execution.md, and the three canonical fixtures still match.