Memtable
De gesorteerde structuur in het werkgeheugen van een LSM-tree waar nieuwe schrijfacties eerst terechtkomen voordat ze naar schijf gaan. Zodra hij vol is, wordt hij “geflusht” naar een onveranderlijke SSTable.
Werking: een schrijfactie gaat naar een write-ahead log (voor crashveiligheid) en naar de memtable, vaak een skiplist of gebalanceerde boom die de sleutels in RAM gesorteerd houdt. Leesacties kijken eerst in de memtable (de nieuwste data). Bereikt de memtable zijn groottelimiet, dan wordt hij alleen-lezen, neemt een nieuwe het over en wordt de oude sequentieel als SSTable weggeschreven. Voordeel: schrijven is snel (RAM plus een sequentieel log, geen willekeurige schijf-I/O) en de flush is een efficiënte sequentiële schrijfactie. Dankzij de WAL kan een niet-geflushte memtable na een crash worden herbouwd. Het onderdeel dat LSM-trees zo snel maakt bij schrijven.