LSM-Tree
Log-Structured-Merge-Tree — die Datenstruktur hinter modernen schreiblastigen Datenbanken. Schreibvorgänge landen zunächst im RAM (Memtable), werden auf Festplatte in unveränderliche sortierte Dateien (SSTables) geschrieben und im Hintergrund kompaktiert.
O'Neil et al. (1996). Schlägt B-Trees bei Schreibvorgängen: sequenzielles statt zufälliges I/O, keine In-Place-Updates. Verliert etwas bei Lesevorgängen (muss mehrere Ebenen prüfen) — ausgeglichen durch Bloom-Filter pro SSTable.
Grundlage von LevelDB, RocksDB, Cassandra, ScyllaDB, HBase, BigTable, DynamoDB, MongoDB WiredTiger, FoundationDB. Stellschrauben: Tiered- versus Leveled-Compaction, Write-/Read-/Space-Amplification.