The MemTable: A Sorted In-Memory Buffer

Every write hits the memtable first. It's a sorted, in-memory map that absorbs writes at RAM speed. Reads check the memtable before any disk file, so freshly-written keys are always visible.

Requirements

A memtable must support:

• put(key, value) — insert or overwrite
• get(key) — return latest value or None
• delete(key) — record a tombstone (covered in Ch 7)
• size() — approximate bytes used (drives flush trigger)
• iter() — yield (key, value) pairs in sorted key order

The sorted iteration is what makes flush easy: we can stream the entries straight into an SSTable without re-sorting.

Why "Sorted"?

Two reasons:

1. Flush is free. An SSTable is a sorted file. If the memtable is already sorted, we just walk it and write.
2. Range queries work. scan('user:100', 'user:200') needs an in-order iterator.

Data Structure Choices

Real systems use skip lists because they're concurrent-friendly (lock-free reads, fine-grained write locks). For learning we'll start with Python's SortedDict from the sortedcontainers library — same O(log n) behaviour, less plumbing.

Sizing & Flush Trigger

Each entry costs roughly len(key) + len(value) + overhead. When the running size exceeds a threshold (LevelDB default: 4 MB, RocksDB default: 64 MB), the memtable is sealed (becomes "immutable") and a new mutable memtable is created. The sealed one is flushed to disk by a background thread.

Implementation Sketch

This is correct but iter() pays a sort cost. In production you'd use a sorted structure so iter() is O(n) walk.