Poznaj różnice między B-tree a LSM-tree w bazach danych. Kiedy wybrać klasyczny indeks drzewa B, a kiedy log-structured merge tree? Przykłady zastosowań i ciekawostki techniczne.

Motywacja B-tree a LSM-tree

Jeśli ktoś Ci mówi, że wszystkie bazy danych działają „tak samo”, to albo próbuje sprzedać Ci własne rozwiązanie, albo dawno nie zaglądał pod maskę (czyt. znam tylko Mongo/MySQL/Postgres/WstawDowolnyInnySystem i dlatego użyjemy jej w projekcie). W świecie storage engines istnieje bowiem pewna fundamentalna różnica, która decyduje o tym, czy baza będzie czytać dane jak błyskawica, czy zapisywać je z prędkością lawiny. Chodzi o dwa podejścia do indeksowania: klasyczne B-tree i nowoczesne LSM-tree.

B-tree

B-tree to stary, sprawdzony mechanizm, w którym dane ułożone są w płaskim, zbalansowanym drzewie. Kiedy chcesz coś odczytać, baza przechodzi przez kilka poziomów drzewa i voilà – masz wynik. Działa to świetnie dla zapytań zakresowych czy odczytów punktowych, bo struktura jest zawsze uporządkowana i dostępna w miejscu.

W B-tree mamy wysoki write amplification, bo każda zmiana może oznaczać zapis całej strony danych. Problem więc zaczyna się, gdy zapisów jest dużo: każda zmiana wymaga aktualizacji odpowiedniego węzła, a to oznacza kosztowne operacje I/O rozrzucone po dysku.

LSM-tree

LSM-tree wybiera zupełnie inną filozofię. Tutaj zapis trafia najpierw do pamięci (tzw. memtable), a dopiero później jest sekwencyjnie dopisywany do plików na dysku, zwanych SSTable. To jak prowadzenie notatek na kartce, a dopiero po czasie przepisywanie ich do ładnego, uporządkowanego zeszytu. Zaletą jest błyskawiczny zapis – operacje są sekwencyjne, więc dysk nie skacze jak podchmielony DJ na imprezie.

W LSM-tree write amplification jest niższy, ale read amplification potrafi rosnąć, gdy liczba SSTable’ów wymaga sprawdzania wielu miejsc naraz. Istnieje też space amplification – dodatkowe zajęcie miejsca na dysku przez starsze wersje danych w LSM, zanim kompaktacja zrobi porządek. Dlatego minusem jest odczyt, bo dane mogą być rozsiane po wielu plikach i trzeba używać sprytnych trików (np. takich jak filtry Blooma, ale to temat na inny wpis), żeby nie przeszukiwać wszystkiego.

B-tree a LSM-tree

B-tree odnajdzie się wszędzie tam, gdzie liczy się natychmiastowy dostęp do danych i częste zapytania są bardziej typowe niż ciągły strumień zapisów. Relacyjne bazy jak PostgreSQL czy MySQL/InnoDB korzystają z tego podejścia, bo gwarantuje ono stabilne czasy odczytu, świetne wsparcie dla transakcji i złożonych zapytań SQL. To idealny wybór dla klasycznych systemów OLTP, gdzie aktualizacje są częste, ale rozłożone w czasie, a konsystencja jest priorytetem.

LSM-tree pokazuje swoją siłę w środowiskach, gdzie zapisów jest więcej niż odczytów, a dane napływają w dużych porcjach. Cassandra, RocksDB czy LevelDB korzystają z tej architektury, bo pozwala ona osiągnąć bardzo wysoki throughput zapisu przy zachowaniu rozsądnej wydajności odczytu. To domena systemów analitycznych, logujących lub rozproszonych, gdzie „eventual consistency” nie jest problemem, a skalowalność w poziomie jest koniecznością.

Kwestia hardware’u

Muszę nadmienić jeszcze, że nowoczesne dyski SSD częściowo niwelują te różnice pomiędzy B-tree a LSM-tree, bo sekwencyjne i losowe I/O zaczynają mieć podobne czasy dostępu, ale na poziomie setek milionów operacji dziennie wciąż widać przewagę odpowiedniego dopasowania silnika do obciążenia. W 2025 roku zaprezentowano mechanizm BVLSM, który rozdziela zapis kluczy i wartości już na etapie dziennika WAL, co przy dużych rekordach dało siedmiokrotny wzrost przepustowości w porównaniu z klasycznym RocksDB.

Podsumowanie

B-tree i LSM-tree to nie konkurenci w wyścigu „który lepszy”, tylko różne narzędzia w tej samej skrzynce. Jeśli Twój system to bank transakcji z tysiącami odczytów na sekundę – wybór jest raczej oczywisty. Jeśli jednak masz serwis przyjmujący miliony logów na minutę – B-tree spoci się szybciej niż LSM-tree. Wybór odpowiedniego storage engine to w praktyce decyzja o tym, jak baza będzie się zachowywać pod realnym obciążeniem, a nie o tym, który algorytm brzmi fajniej w dokumentacji lub w której bazie spędziłeś/aś ostatnie pięć lat.