I am reading LSM indexing in Designing Data-Intensive Applications by Martin Kleppmann.
The author states:
When a write comes in, add it to an in-memory balanced tree data structure (for example, a red-black tree). This in-memory tree is sometimes called a memtable.
When the memtable gets bigger than some threshold—typically a few megabytes —write it out to disk as an SSTable file. This can be done efficiently because the tree already maintains the key-value pairs sorted by key. The new SSTable file becomes the most recent segment of the database. While the SSTable is being written out to disk, writes can continue to a new memtable instance.
In order to serve a read request, first try to find the key in the memtable, then in the most recent on-disk segment, then in the next-older segment, etc.
From time to time, run a merging and compaction process in the background to combine segment files and to discard overwritten or deleted values.
My question is: given that SSTables on disk are immutable, how is sorting guaranteed when new data comes in, that can change the ordering of data in SSTables (not memtable which is in memory)?
For e.g., suppose we have a SSTable on disk which has key-values pairs like [{1:a},{3:c},{4,d}]. Memtable in memory contains [{5,e},{6,f}] (which is sorted using AVL/RB tree). Suppose we now get a new entry: [{2,b}] which should reside between [{1:a}] and [{3:c}]. How would this be handled, if SSTable(s) on disk are immutable? In theory, we could create a new SSTable with [{2,b}] and compaction could later merge them, but wouldn't that break range-queries/reads that we perform before compaction takes place?
Thanks!