Arbre LSM
Log-Structured Merge tree — la structure de données au cœur des bases modernes à forte charge en écriture. Les écritures atterrissent d'abord en mémoire (memtable), sont vidées vers des fichiers triés immuables sur disque (SSTables), puis compactées en arrière-plan.
Décrit par O'Neil et al. (1996). Bat les arbres B en écriture : des E/S séquentielles plutôt qu'aléatoires, et aucune mise à jour sur place. Perd un peu en lecture (il faut consulter plusieurs niveaux) — compensé par un filtre de Bloom par SSTable.
Sous-tend LevelDB, RocksDB, Cassandra, ScyllaDB, HBase, BigTable, DynamoDB, WiredTiger de MongoDB et FoundationDB. Les réglages en jeu : compaction par paliers (tiered) ou par niveaux (leveled), et les amplifications d'écriture, de lecture et d'espace.