The Core Shape
A log structured merge tree absorbs writes into an in memory table called a memtable. When the memtable fills, it is flushed to disk as an immutable sorted file. These files accumulate, so a background process merges them to keep reads fast and reclaim space.
Levels
In a leveled organization the on disk files are grouped into levels numbered from zero. Level zero holds freshly flushed files that may overlap in key range. Each deeper level holds files that do not overlap and is many times larger than the one above it.
- A write touches only memory plus a log, so it is cheap.
- A read may check several levels until it finds the key.
- Merging pushes data downward, level by level.
Tiers
A tiered organization instead groups several similarly sized runs into a tier, then merges a whole tier at once into one larger run in the next tier. This writes data fewer times but lets more runs pile up.
Key idea
An LSM tree buffers writes in memory and flushes sorted runs that merge into ever larger levels or tiers, trading extra background work for fast sequential writes.