MemTable
The in-memory write buffer at the heart of every LSM database
Loading section...
The in-memory write buffer at the heart of every LSM database
SST files are immutable — where do writes go?
Strategy
Why this fails
SST files store sorted data in sealed blocks. Inserting a new key means:
For a 64MB SST, every write triggers a full rewrite. This destroys throughput.
SST files are immutable by design — once sealed, they never change. This makes reads fast (no locking, no COW) but makes direct writes impossible. The MemTable solves this: a mutable, in-memory sorted structure that absorbs all incoming writes at RAM speed.
But what data structure inside the MemTable keeps entries sorted while allowing fast inserts? A sorted array won't work (O(n) inserts), and a hash map loses ordering. We need something better.