SSTable
Sorted String Table: file immutabile di coppie chiave-valore memorizzate su disco in ordine. L'unità di archiviazione fondamentale dei database basati su LSM-tree (Bigtable, Cassandra, RocksDB, LevelDB).
Come funziona: quando una memtable si riempie viene scritta come nuova SSTable, ordinata e immutabile (non viene mai riscritta, solo sostituita durante la compaction). L'ordinamento consente la ricerca binaria e scansioni di intervalli efficienti; ogni SSTable ha di solito un indice sparso interno e un filtro di Bloom per escludere rapidamente le chiavi assenti. L'immutabilità rende la scrittura sequenziale (veloce) e semplifica la concorrenza, perché non servono lock in lettura. Lo svantaggio: la stessa chiave può comparire in più SSTable nel tempo, quindi serve la compaction per unirle e ripulirle. Il concetto deriva dal paper di Google su Bigtable (2006) ed è una pietra angolare dei moderni database NoSQL e dei key-value store embedded.