LSM-tree
Log-Structured Merge tree: la struttura dati dietro i database moderni orientati alla scrittura. Le scritture arrivano prima in RAM (memtable), vengono svuotate in file ordinati e immutabili su disco (SSTable) e compattate in background.
Proposta da O'Neil e altri (1996). Batte i B-tree in scrittura: I/O sequenziale invece che casuale, nessun aggiornamento sul posto. Perde un po' in lettura (bisogna controllare più livelli), compensato da un bloom filter per ogni SSTable.
Sta alla base di LevelDB, RocksDB, Cassandra, ScyllaDB, HBase, BigTable, DynamoDB, WiredTiger di MongoDB e FoundationDB. Le manopole di taratura: compattazione tiered o leveled, amplificazione di scrittura, lettura e spazio.