LSM-дерево и таблицы отсортированных строк

Коротко: LSM-дерево сначала собирает записи в памяти и записывает их на диск пачками и в отсортированном виде. Это делает запись очень быстрой; чтение требует больше работы.

Подробнее: Новые данные попадают в memtable (отсортированную в ОЗУ) и в журнал упреждающей записи. Когда memtable заполнена, она сохраняется как неизменяемый отсортированный файл (SSTable). В фоне уплотнение (compaction) сливает множество мелких файлов в более крупные и удаляет устаревшие значения.

Подробности

• Чтение: сначала memtable, затем SSTable…

См. также: B-дерево и B+-дерево, журнал упреждающей записи и восстановление