Что такое LSM-дерево и чем оно отличается от B-дерева?

Путь записи:

1. запись добавляется в конец журнала (WAL) — для надёжности;
2. кладётся в memtable — отсортированную структуру в памяти (skip list, красно-чёрное дерево);
3. когда memtable заполнилась, она целиком записывается на диск как SSTable — отсортированный по ключу неизменяемый файл с индексом и фильтром Блума. Это одна последовательная запись.

Обновление и удаление — тоже новые записи: новая версия ключа или надгробие (tombstone). Старое значение остаётся в старых файлах.

Путь чтения: memtable → свежие SSTable → старые; первое найденное значение — актуальное. Чтобы не открывать каждый файл, у каждого есть фильтр Блума («ключа здесь точно нет» или «возможно есть») и разреженный индекс.

Compaction. Файлов становится много, в них устаревшие версии и надгробия. Фоновое слияние объединяет несколько SSTable в одну — это слияние отсортированных последовательностей, как в сортировке слиянием, с отбрасыванием устаревшего. Стратегии:

• по размеру (size-tiered) — сливаем файлы похожего размера; мало перезаписи, но много файлов на чтение и временно двойное место;
• по уровням (leveled) — каждый уровень в ~10 раз больше предыдущего, ключи на уровне не пересекаются; чтение быстрее, но больше перезаписи.

Усиления (amplification) — главный язык сравнения:

• записи — сколько байт реально пишется на байт данных (данные переписываются при слиянии): у LSM 10–30, у B-дерева — переписывается целая страница ради одной строки;
• чтения — сколько файлов или страниц читается на запрос: у B-дерева обычно меньше;
• места — сколько лишнего хранится: устаревшие версии в LSM до слияния, недозаполненные страницы в B-дереве.

Когда LSM: много записей и последовательная запись важнее (журналы событий, метрики, временные ряды, счётчики, сообщения), SSD с ресурсом записи, сжатие (неизменяемые файлы хорошо сжимаются). Когда B-дерево: смешанная OLTP-нагрузка, много точечных чтений и диапазонов, предсказуемая задержка — compaction в LSM может давать всплески задержки.

put(k7, v1)  → WAL, memtable {k7: v1}
put(k3, v2)  → WAL, memtable {k3: v2, k7: v1}
memtable полна → SSTable-1 [k3: v2, k7: v1]
put(k7, v3), delete(k3) → memtable {k3: ✝, k7: v3} → SSTable-2
get(k7): memtable → SSTable-2 (v3) — найдено, в SSTable-1 не смотрим
compaction(1, 2) → SSTable-3 [k7: v3]   — старая версия и k3 исчезли