Log-Structured Merge Tree
Ein LSM-Baum hängt Schreibvorgänge an eine In-Memory-Tabelle an und schreibt diese bei Füllung in unveränderliche SSTables; mehrstufige Kompaktierung balanciert Schreibdurchsatz gegen Leseverstärkung.
Zweck
Verständnis der zentralen Datenstruktur schreibintensiver Speicher-Engines, verwendet in LevelDB/RocksDB/Cassandra.
Mechanismus
Schreibvorgänge gehen in eine MemTable (Skip-List im Speicher); ist sie voll, wird sie in eine L0-SSTable geleert. Lesevorgänge verschmelzen alle SSTables + die MemTable. Kompaktierung führt benachbarte Ebenen zusammen, um die Leseverstärkung zu senken. LSM-Sequenzschreibvorgänge optimieren den Durchsatz auf Kosten von Lese- und Raumverstärkung.
Anwendungsfälle
- Design schreibintensiver Speicher
- SSTable-Optimierung
- LSM-Kompaktierung