/ The Arena

Landmark Capstone Challenge: LSM-Tree Storage Engine ⚔️

In this landmark capstone challenge, you will implement a complete Log-Structured Merge-Tree (LSM-Tree) Storage Engine featuring an active MemTable, immutable SSTables, and Bloom Filter lookups.

Requirements:

1. Active MemTable & Sequential Flush:
   • Store incoming put and delete operations in memory.
   • When memTable.size >= memTableThreshold, flush entries into an immutable SSTable, sorted lexicographically by key.
2. Bloom Filter Optimization:
   • Generate a Bloom Filter for each flushed SSTable.
   • Before scanning an SSTable, query its Bloom Filter to skip disk reads for non-existent keys.
3. Multi-SSTable Read Precedence & Tombstones:
   • Query in order: Active MemTable $\to$ SSTables (newest to oldest).
   • Correctly interpret null tombstone records as deleted keys.