LSM-tree vs B-Tree

Структуры данных для индексирования на диске: B-Tree (InnoDB, PostgreSQL) – сбалансированное дерево, данные хранятся в упорядоченных страницах, хорошие времена чтения по ключу и диапазону, но при записи обновляет страницы in-place (может быть рандомный I/O); LSM-tree (Cassandra, ClickHouse) – лог-структурированное слияние: все новые записи пишутся последовательно в конец (в память (MemTable), затем на диск как сортированные SSTables), чтения собирают данные из нескольких файлов, периодически фоновые compaction сливают файлы и удаляют старые версии; LSM даёт высокую пропускную способность вставки/записи (последовательный I/O) и отличное сжатие, но чтения сложнее (может потребоваться заглянуть в N файлов) и паузы на compaction; выбор движка зависит от нагрузки: write-heavy с большим объемом – LSM, read-heavy с частыми выборками по индексам – B-Tree.