An LSM-tree (Log-Structured Merge-tree) is the storage engine behind RocksDB, and the write path underneath Cassandra, ScyllaDB, and many other write-optimized databases. Writes always go to an in-memory memtable first (fast, no disk I/O). Once it's full, it flushes to an immutable, on-disk SSTable, and a fresh memtable starts. Periodically, SSTables get COMPACTED -- merged together, keeping only the newest value per key -- to bound how many places a read has to check.

The missing link: deleting doesn't mean "remove"

SSTables are immutable once written -- you can't reach into an old one and erase a key. So what does delete(key) even do if an older sstable still has a real value for that key sitting on disk? Simply removing key from the memtable isn't enough: get() would find nothing in the memtable and fall through to the sstables, where the OLD value is still sitting there waiting to be resurrected. A delete has to be recorded as an actual event -- a tombstone -- written and flushed through the exact same path as a real value, so it can shadow an older sstable's entry the same way a newer put() would. compact() has to respect tombstones too: merging must never let an older table's real value win just because the newer table's entry "looks empty."

put()/flush() are done for you. Implement:

• delete(key): record a tombstone for key (reuse put's memtable/flush path -- a tombstone is written and flushed exactly like a value).
• get(key): check the memtable first, then SSTables from NEWEST to OLDEST (self.sstables[-1] is newest). The first place key is found anywhere wins -- if that's a tombstone, the key is deleted (None). If not found anywhere, also None.
• compact(): merge ALL SSTables into ONE, oldest to newest, so a newer table's entry (value OR tombstone) always overwrites an older one for the same key. Tombstones must survive compaction as tombstones.

Example

lsm = LSMTree(memtable_limit=100)
lsm.put("a", "v1")
lsm.flush()
lsm.delete("a")
lsm.get("a")          # -> None (tombstone shadows the flushed value)
lsm.compact()
lsm.get("a")          # -> still None (tombstone survived the merge)

Constraints

• get must check the memtable before ANY sstable -- the memtable always has the freshest data (which may itself be a tombstone).
• compact must merge SSTables in OLDEST-to-NEWEST order so a later merge (from a newer table) overwrites an earlier one -- for both real values and tombstones.
• A tombstone is not the same thing as a missing key, and not the same thing as a stored value of None -- don't conflate any of the three.

Real-world grounding

• RocksDB's overall LSM-tree design (memtables, SSTables, compaction) is documented across its wiki and source: facebook/rocksdb
• RocksDB's delete/tombstone handling during compaction: db/dbformat.h (see kTypeDeletion)

Real LSM-trees add more on top of this: multiple compaction strategies (leveled vs. tiered, trading write amplification against read amplification), Bloom filters per SSTable to skip ones that definitely don't contain a key without even opening them, and eventually GARBAGE COLLECTING a tombstone once compaction has confirmed no older data for that key survives anywhere -- but "newest write wins, check memory before disk, and a delete is a real record, not an erasure" is the core idea underneath all of it.