b-tree-vs-lsm.js·4 scenarios
B-tree vs LSM-tree storage engines comparison: B+tree with in-place updates, page splits, WAL (Postgres/MySQL) vs LSM with memtable, SSTables, leveled compaction, bloom filters (RocksDB/Cassandra). Scenarios: B-tree page split, LSM write-flush-compact, point query latency comparison, delete semantics with tombstones.
Выбор storage engine — самое фундаментальное архитектурное решение базы данных. От него зависит, на каком workload она будет сиять, а на каком — задыхаться. Все мейнстримные движки делятся на два больших семейства: B-tree (in-place updates, read-optimized) и LSM-tree (append-only, write-optimized). Postgres, MySQL InnoDB, Oracle, SQL Server, SQLite, FoundationDB — все они B-tree. Cassandra, RocksDB, LevelDB, ScyllaDB, HBase, BigTable, DynamoDB — все LSM. Этот раздел существует не для того, чтобы запомнить «кто к какому семейству относится», а чтобы научиться смотреть на workload и предсказывать, какая семья даст лучший throughput, лучшую latency, лучшую space efficiency.
Без этого понимания случаются типичные провалы: команда берёт Cassandra под mixed OLTP-нагрузку с tight tail-latency SLA, потому что «современная и масштабируется», а потом ловит p99 в секундах из-за compaction spikes. Или наоборот — пихают миллиард событий в день в Postgres, удивляются bloat, vacuum съедает 30% I/O, и через полгода миграция на Kafka + ClickHouse. Главное оружие против таких ошибок — понимать физику того, как row update превращается в disk I/O в каждом из миров.
B-tree кладёт данные аккуратно на место — read предсказуем, write дорогой. LSM пишет всё в стопку, а потом разбирает в фоне — write мгновенный, read и disk usage пляшут.
Глубже: B-tree держит на диске сбалансированное дерево фиксированных страниц (обычно 8KB), где каждая страница — заполненный массив отсортированных записей. Чтение — спуск от root через несколько internal pages до leaf, 3-4 page reads на любой ключ, predictable. Запись — найти нужную leaf page, переписать её целиком, плюс при переполнении сделать split (новая страница + обновление родителя), плюс WAL для durability. Каждый INSERT одной 100-байтной строки честно стоит 24KB+ disk I/O в худшем случае.
LSM-tree выворачивает это наизнанку. Запись падает в memtable (sorted skiplist в RAM) + WAL — O(log N) без disk seek, ~50μs ответ. Memtable растёт до threshold, потом flush превращает её в immutable SSTable на диске (одна большая sequential запись). SSTables со временем накапливаются на «уровне 0»; background compaction периодически сливает несколько SSTables в один больший, поднимаясь по уровням L1, L2, ..., L6. Чтение — проверить memtable, потом пройтись по всем SSTables (bloom filter отсеивает большинство), достать самое свежее значение для ключа. Append-only мантра даёт нулевое write amplification в моменте, но потом приходится платить compaction'ом — каждая запись копируется через все уровни, lifetime write amp ~10-30×.
Запомните три цифры, по которым семейства различаются на порядки:
| B-tree | LSM-tree | |
|---|---|---|
| Write amplification | 3-10× (page rewrite) | 10-30× (compaction), но sequential |
| Read amplification | 3-4 page reads | 1-N SSTable lookups (bloom гасит) |
| Space amplification | 1.1-1.5× (slack + bloat) | 1.5-2× в момент compaction |
| Latency tail (p99) | predictable | spiky (compaction stop-the-world) |
Канвас разделён на два мира. Сверху — B-tree storage engine (Postgres / MySQL InnoDB / SQLite): SQL-клиент бьётся в buffer pool (LRU-кеш страниц в RAM), оттуда write идёт в WAL (sequential append с fsync), а структура самих данных — классическое B+tree: root → internal → leaf-A / leaf-B / leaf-C. Leaf-страницы связаны цепочкой (для range scan), Leaf B специально помечена «FULL!» — на этом примере в Scenario 1 произойдёт page split.
Снизу — LSM-tree storage engine (RocksDB / Cassandra / HBase): KV-клиент пишет одновременно в WAL и в memtable (skiplist в RAM). Из memtable периодически идёт flush в L0 SSTables (immutable). Bloom filter лежит рядом с каждой SSTable в RAM. Для read клиент сначала проверяет bloom, потом ходит в нужные SSTable. Compaction worker — отдельная background-нода, которая мерджит L0 → L1 → L2, поддерживая sorted non-overlapping ranges на нижних уровнях.
ADR-001 и ADR-002 закреплены на ноде btree-root — там разобраны критерии выбора семейства и кто платит за уборку (vacuum vs compaction).
INSERT в полную leaf page показывает истинную цену B-tree write. SQL-клиент кладёт (id=75, name=Alice), ключ маршрутизируется через root → internal → leaf-B. Leaf-B уже забита (50 rows на 8KB), новой записи места нет. Storage engine выделяет новую страницу (B2), перераспределяет половину rows из B в B2, обновляет ptr в parent internal page (новый разделитель ключ=76). Если internal тоже переполнен — split рекурсивно поднимается до root. Всё это попадает в WAL: 3 dirty pages × 8KB = 24KB I/O на 100-байтную row. Это write amplification ~240× в худшем случае. На массовом INSERT-нагрузке B-tree «греется» именно этим.
Зеркальный сценарий для LSM. PUT падает в WAL (sequential append, fsync) и в memtable (skiplist) — ~50μs ответ. Клиент продолжает писать в новые memtables, старые при переполнении (~64MB) flush'атся одним sequential write как immutable SSTable в L0. Memtable ротация не блокирует writes. Со временем накапливается несколько L0 SSTables с overlapping ranges — это проблема для read (нужно проверить каждый L0). Background compactor забирает overlapping L0 + overlapping L1 SSTables, делает K-way merge (sorted iteration, newer-wins, tombstones применены), записывает результат как новые L1 SSTables (non-overlapping ranges), удаляет старые. Каскад продолжается L1 → L2 → ... В моменте compaction'а disk usage 2× (старые + новые сосуществуют), CPU + disk burst. Lifetime write amplification ~10-30×, но всё это sequential — SSD счастлив, throughput высокий.
Прямое сравнение latency. B-tree GET: если page в buffer pool — 100ns hit. Cache miss — descend root → internal → leaf, 3-4 page reads, p50 ~100μs, p99 ~500μs. Распределение узкое и предсказуемое — если working set влезает в RAM, tail latency почти нет. LSM GET: проверяем active memtable (1μs если hit). Потом проходим bloom filters перед каждой SSTable: NO → skip без I/O, MAYBE → читаем index block + data block (~150μs SSD). L0 SSTables могут все содержать ключ (overlapping); L1+ — максимум один per range. p50 ~50μs (bloom catches everything), но p99 ~5ms из-за bloom false positives (~1%), cold SSTables, и — главное — compaction в работе крадёт disk I/O. Вывод: LSM быстрее median, но хуже tail; для OLTP с tight SLA — B-tree, для write-heavy ingest — LSM.
Самое контр-интуитивное различие. B-tree DELETE (Postgres MVCC): помечает tuple xmax = current_txid, физически row остаётся в page. Освобождает место VACUUM в фоне. Без vacuum — table bloat, dead tuples жрут seq scan. LSM DELETE: пишет новую запись (key, value=TOMBSTONE). Да, delete = write. Tombstone flush'ится в SSTable как обычная запись. На read tombstone «побеждает» старое значение → клиент получает NOT_FOUND. При compaction tombstone «съедает» старую запись — только тогда место реально освобождается. Антипаттерн «tombstone hell»: queue-like workload на Cassandra (массовый INSERT-then-DELETE) накапливает миллионы tombstones, read становится медленным, compaction не успевает. Плюс zombie problem: если tombstone GC'нется до того как дойдёт до последнего level, старое значение из L2 «воскреснет». Cassandra решает это gc_grace_seconds (default 10 дней) — tombstone живёт дольше repair interval.
Контекст. Storage engine определяет фундамент. Workload может быть mixed OLTP с predictable read tail (банкинг, e-commerce checkout), write-heavy ingest (IoT, logs, time-series), или read-heavy analytics (BI dashboards). Один engine не побеждает на всех — приходится выбирать.
Решение по умолчанию — B-tree (Postgres) для:
WHERE created_at BETWEEN)Перейти на LSM (RocksDB / Cassandra) когда:
Гибридные решения:
Кто платит за уборку (ADR-002):
| B-tree (Postgres) | LSM (RocksDB) | |
|---|---|---|
| Cleanup механизм | VACUUM | Compaction |
| Когда запускается | Auto on bloat threshold | Auto on level overflow |
| Конкурирует за | I/O bandwidth | I/O + CPU |
| Дисковый headroom | +20% (slack) | +30-50% (compaction temp) |
| Tuning knob | autovacuum_* | level0_file_num_compaction_trigger, max_bytes_for_level_multiplier |
| Худший сценарий | VACUUM FULL lock + rewrite | Compaction backlog → write stall |
Анти-решение: «возьмём LSM, потому что модно и масштабируется». LSM не магически масштабируется — он масштабируется на специфическом классе нагрузок (write-heavy). Для read-heavy OLTP это шаг назад: latency tail хуже, compaction жрёт I/O, операционная сложность выше.
B-tree семейство:
LSM семейство:
VACUUM FULL под нагрузкой. Vacuum — не баг, это часть рабочего цикла.bloom_filter_fp_chance = 0 в Cassandra «для максимальной точности». На самом деле это выключает bloom filter (FPR 100%), read становится в разы медленнее. Хотите больше точности — ставьте 0.001, не 0.pg_stat_activity.xact_start.Не B-tree, когда:
Не LSM, когда:
Ни тот, ни другой:
Книги:
Papers:
Production docs:
Связанные темы: