🗃️ B-drzewo — wielokierunkowe drzewo wyszukiwań

O strukturze indeksu B-drzewa

B-drzewo rzędu m to samobalansujące się drzewo wyszukiwania wielodrożnego, w którym każdy węzeł przechowuje od ⌈m/2⌉−1 do m−1 kluczy oraz od ⌈m/2⌉ do m wskaźników do dzieci. Klucze w każdym węźle są utrzymywane w kolejności posortowanej, a wskaźniki do dzieci oddzielają kolejne przedziały kluczy, dzięki czemu wyszukiwanie wymaga zejścia najwyżej przez O(log_⌈m/2⌉ n) węzłów, by odnaleźć dowolny klucz — zwykle zaledwie 2–4 węzły dla indeksu bazy danych z milionem rekordów. Ta minimalna liczba odwiedzanych węzłów jest podstawowym powodem, dla którego bazy danych stosują B-drzewa: każde odwiedzenie węzła odpowiada jednemu odczytowi strony dysku, więc utrzymywanie płytkiego drzewa minimalizuje najkosztowniejszą operację w systemach przechowywania danych.

Symulacja implementuje prawdziwe B-drzewo z wstawianiem opartym na podziale przy przepełnieniu. Możesz wybrać rząd m (3–6), wpisywać lub generować losowe klucze całkowite oraz obserwować, jak węzły zapełniają się i dzielą w czasie rzeczywistym. Po każdym podziale klucz środkowy jest podświetlany, dzięki czemu widać, jak jest on przenoszony do węzła rodzica. Panel statystyk pokazuje na żywo rząd, wysokość, liczbę węzłów, liczbę kluczy oraz łączną liczbę podziałów. Wypróbuj rząd 3, aby zobaczyć częste podziały, albo przełącz na rząd 6, by sprawdzić, jak większe węzły opóźniają konieczność podziału.