LSM-tree
Log-Structured Merge tree — a estrutura de dados por trás dos bancos modernos com muita escrita. As escritas caem primeiro na RAM (memtable), são despejadas em arquivos ordenados imutáveis (SSTables) no disco e compactadas em segundo plano.
O'Neil et al. (1996). Supera as B-trees em escrita: E/S sequencial em vez de aleatória, sem atualização in-place. Perde um pouco na leitura (precisa consultar vários níveis), compensado com bloom filters por SSTable.
Sustenta LevelDB, RocksDB, Cassandra, ScyllaDB, HBase, BigTable, DynamoDB, MongoDB WiredTiger e FoundationDB. Parâmetros de ajuste: compactação em camadas (tiered) ou por níveis (leveled), amplificação de escrita, leitura e espaço.