An LSM tree, or log-structured merge tree, is a balanced binary search tree in which each node has a key and contains a value. (This value could be actual data or a memory address, see co-locating data for details).
Info
LSM trees are typically constructed with data structures like red-black trees or AVL trees.
Just like a b-tree, each non-leaf node contains ranges along with pointers to children nodes, while each leaf node contains key-value pairs.
Under normal database operation, the entire LSM tree lives in-memory, and new data is written to it in time.
Once the LSM tree grows too large for memory, it is written to disk as an SSTable, or sorted-string table and then cleared. An SSTable is simply a list of key-value pairs that are sorted by key.
Info
The LSM tree is also sometimes called the memtable.
reading from the index
To read, we first binary search the LSM tree. If no results are found, we iterate in reverse-chronological order through the SSTables on disk.
See optimizations for details on how SSTable reads and storage are optimized.
pros
- Can be stored on disk.
- Faster writes than b-trees because we first write to memory.
cons
- Range queries require searching through LSM tree and all SSTables.
- This is still faster than hash indexes, because the tree and tables are all sorted.
- Compaction in the background requires extra CPU usage.
optimizations
sparse indexes
Now that all of our data is sorted in SSTables, we can have sparse indexes over top of each SSTable. This further improves the search of each SSTable to below , because we can find a nearby key and linear scan from there.
bloom filter
TODO: research more into this