B-drzewa: dlaczego indeks w bazie nie jest zwykłym drzewem

W poprzedniej części zbudowaliśmy drzewo, które trzyma porządek i ma wysokość O(log n). Wszystko pięknie – dopóki dane mieszczą się w pamięci. Gdy przestają, zmienia się jednostka rozliczeniowa: nie liczymy już porównań, tylko odczyty z dysku. A wtedy okazuje się, że drzewo binarne jest jedną z najgorszych możliwych struktur.

Arytmetyka, która zmienia wszystko

Dysk (także SSD) nie czyta pojedynczych bajtów. Czyta strony – bloki o stałym rozmiarze. W InnoDB, silniku MySQL-a, strona ma domyślnie 16 KB (innodb_page_size). Odczyt jednego bajtu i odczyt szesnastu kilobajtów kosztuje praktycznie tyle samo.

Weźmy tabelę z miliardem wierszy:

• Drzewo binarne ma wysokość log₂(10⁹) ≈ 30. Każdy węzeł to dwa klucze i dwa wskaźniki, czyli kilkadziesiąt bajtów – ale leży pod losowym adresem, więc każde zejście o poziom to osobny odczyt strony. Trzydzieści odczytów na jedno wyszukanie.
• B-drzewo upycha w jednym węźle tyle kluczy, ile zmieści się na stronie. Przy kluczu 8-bajtowym i wskaźniku tej samej wielkości w 16 KB mieści się rzędu tysiąca pozycji. Wysokość to log₁₀₀₀(10⁹) = 3.

Trzy odczyty zamiast trzydziestu – i to jest cała idea B-drzewa, wymyślonego w 1970 roku przez Bayera i McCreighta właśnie z myślą o pamięci masowej. Nie chodzi o mniejszą liczbę porównań (tych jest podobnie, bo w węźle też trzeba szukać), tylko o mniejszą liczbę dotknięć dysku.

Poniżej dla porównania drzewo binarne na piętnastu elementach – zwróć uwagę na wysokość przy zaledwie kilkunastu wartościach i pomnóż to sobie w wyobraźni przez miliard:

B-drzewo i B+ drzewo

Klasyczne B-drzewo trzyma dane we wszystkich węzłach. Bazy danych używają jednak wariantu B+, w którym:

• wszystkie dane leżą w liściach, a węzły wewnętrzne zawierają wyłącznie klucze nawigacyjne (dzięki czemu mieści się ich w węźle jeszcze więcej),
• liście są połączone w listę, więc po znalezieniu początku przedziału można iść w prawo bez wracania do korzenia.

Ta druga cecha to powód, dla którego zapytanie WHERE data BETWEEN … AND … jest tak tanie: baza schodzi raz do liścia i dalej czyta sekwencyjnie.

Jak to wygląda w MySQL-u

W InnoDB każda tabela jest B+ drzewem, uporządkowanym według klucza głównego – to tak zwany indeks klastrowy. Wiersze nie leżą „gdzieś obok” indeksu; one są jego liśćmi. Stąd kilka praktycznych wniosków:

• Klucz główny powinien być krótki i rosnący. Losowy UUID jako PK oznacza wstawianie w środek drzewa, dzielenie stron i fragmentację. Klucz rosnący (AUTO_INCREMENT, UUID w wersji 7) dopisuje zawsze na końcu.
• Indeks wtórny przechowuje wartość klucza głównego, a nie wskaźnik do wiersza. Znalezienie wiersza po indeksie wtórnym to więc dwa przejścia: przez indeks wtórny do PK i przez indeks klastrowy do danych. Długi klucz główny puchnie we wszystkich indeksach naraz.
• Indeks pokrywający (covering index) to taki, który zawiera wszystkie kolumny potrzebne w zapytaniu – wtedy drugie przejście odpada, bo baza czyta odpowiedź prosto z liścia indeksu.

-- MySQL
CREATE INDEX idx_zamowienia_klient_data ON zamowienia (klient_id, data_utworzenia);

-- Skorzysta z indeksu (lewy prefiks + zakres na drugiej kolumnie):
SELECT * FROM zamowienia WHERE klient_id = 42 AND data_utworzenia >= '2026-08-01';

-- Skorzysta częściowo (tylko pierwsza kolumna):
SELECT * FROM zamowienia WHERE klient_id = 42;

-- NIE skorzysta: pominięty lewy prefiks
SELECT * FROM zamowienia WHERE data_utworzenia >= '2026-08-01';

Reguła lewego prefiksu wynika wprost z tego, jak posortowane są klucze w drzewie: indeks złożony porządkuje wiersze najpierw po pierwszej kolumnie, potem po drugiej – dokładnie jak spis nazwisk uporządkowany po nazwisku, a dopiero potem po imieniu. Szukanie po samym imieniu w takiej książce jest bezużyteczne.

Kiedy indeks nie pomoże

To najbardziej praktyczna część całego wpisu, bo tu ląduje większość zapytań, które „nagle zwolniły”:

1. Funkcja na kolumnie. WHERE YEAR(data) = 2026 nie użyje indeksu na data, bo indeks przechowuje daty, a nie ich lata. Zapisz to jako zakres: data >= '2026-01-01' AND data < '2027-01-01'.
2. Wzorzec zaczynający się od znaku wieloznacznego. LIKE '%kowalski' – indeks porządkuje od początku napisu, więc nie ma od czego zacząć. LIKE 'kowalski%' zadziała.
3. Niska selektywność. Indeks na kolumnie z dwiema wartościami (aktywny/nieaktywny) zwykle nie pomaga – baza słusznie uzna, że taniej przeskanować tabelę niż skakać do połowy wierszy przez indeks.
4. Niezgodność typów. Porównanie kolumny tekstowej z liczbą wymusza konwersję i unieważnia indeks.
5. Mała tabela. Kilkaset wierszy mieści się na kilku stronach – skan jest wtedy szybszy niż nawigacja po drzewie.

Diagnoza zawsze wygląda tak samo: EXPLAIN przed zapytaniem i spojrzenie na kolumnę type. const i ref znaczą, że indeks działa; range – że działa dla przedziału; index – że baza czyta cały indeks; ALL – że czyta całą tabelę. Dwa ostatnie przy dużej tabeli to sygnał ostrzegawczy.

Sortowanie, którego nie ma

Na koniec klamra do serii o algorytmach sortowania. Skoro indeks przechowuje klucze w porządku, to zapytanie:

-- MySQL
SELECT * FROM zamowienia WHERE klient_id = 42 ORDER BY data_utworzenia;

przy indeksie (klient_id, data_utworzenia) nie sortuje niczego. Baza po prostu czyta liście w kolejności, w której już leżą. W EXPLAIN widać to po braku Using filesort – a filesort to nic innego jak sortowanie zewnętrzne, o którym pisałem w ostatniej części tamtej serii: jeśli wynik nie mieści się w pamięci, MySQL zapisuje porcje na dysk i scala je.

To jest najlepsza możliwa puenta dla obu serii: najszybszy sort to ten, którego nie trzeba wykonać – bo ktoś zadbał o porządek wcześniej, przy zapisie.

W następnej części zajmiemy się strukturą, która nie utrzymuje pełnego porządku, a tylko pilnuje, żeby na wierzchu zawsze był element najważniejszy. Brzmi skromnie, a bez niej nie działałby ani scheduler, ani wyznaczanie tras.