Drzewa B: Indeks stojący za każdą bazą danych

Zastosowanie drzewa dla wolnego przechowywania

Drzewo czerwono-czarne jest zoptymalizowane pod kątem minimalizacji porównań w pamięci RAM. Drzewo B (Bayer i McCreight, 1972) jest zoptymalizowane pod kątem innego celu: minimalizacji liczby odczytów dyskowych, które są znacznie wolniejsze niż jakiekolwiek operacje w pamięci. Zamiast jednego klucza na węźle, drzewo B o zamówieniu m pakuje wiele kluczy w każdym węźle – wystarczająco dużo, aby wypełnić dokładnie jedną stronę dysku lub linię bufora – więc pojedynczy wolny odczyt pobiera jednocześnie dużą ilość informacji związanych z setkami porównań.

order m B-tree, every non-root node holds:
  between ceil(m/2) - 1  and  m - 1   keys
  between ceil(m/2)      and  m       children (internal nodes)

keys inside a node are sorted; the k+1 children of a node with k keys
"straddle" the k keys, so child[i] holds keys strictly between
key[i-1] and key[i]

Wstawienie: wypełnij, podziel środkiem, przesuń w górę

Nowy klucz jest wstawiany do odpowiedniego liścia, zachowując go w uporządkowanym stanie. Jeśli ten liść teraz zawiera m kluczy – jeden za dużo – dzieli się: klucz środkowy przemieszcza się w górę do rodzica, a klucze po jego obu stronach stają się dwa oddzielne, częściowo wypełnione węzły.

insert(key): liść = znajdź_liście(key) wstaw klucz do liścia, zachowując go w uporządkowanym stanie while liść.keyCount == m: // przepełniony, musi się podzielić mid = liść.keys[m / 2] // klucz środkowy lewy, prawy = podziel liść wokół mid jeśli liść nie ma rodzica: utwórz nowy korzeń z mid, dzieci [lewy, prawy] // drzewo rośnie +1 poziom else: wstaw mid do liścia.parent, zastąp liść [lewym, prawym] liść = liść.parent // podział może rozchodzić się w górę Kluczowa uwaga brzmi, że drzewo B rośnie tylko w górę, przez dzielenie korzenia, więc każdy liść zawsze pozostaje na dokładnie tej samej głębokości – nie ma liścia, który jest głębszy niż inny, w przeciwieństwie do niezbalansowanego drzewa binarnego.

insert(key):
  leaf = find_leaf(key)
  insert key into leaf, keeping it sorted
  while leaf.keyCount == m:               // overfull, must split
    mid = leaf.keys[m / 2]                 // median key
    left, right = split leaf around mid
    if leaf has no parent:
      create new root with mid, children [left, right]  // tree grows +1 level
    else:
      insert mid into leaf.parent, replace leaf with [left, right]
      leaf = leaf.parent                   // the split may cascade upward

Dlaczego wysokość ledwo mierzy się jako logarytmiczna

Wysokość drzewa B jest równa O(log_m n), gdzie m to współczynnik gałęzi, a nie 2. Czerwone-czarne drzewo z milionem kluczy ma wysokość około 2·log2(1000000) ≈ 40. Drzewo B o zamówieniu 200 przechowujące te same miliony kluczy ma wysokość około log_200(1000000) ≈ 2,6 – w zasadzie 3 poziomy. Ta różnica jest całą przyczyną istnienia drzew B: wybierając wystarczająco duże m, aby dopasować je do strony dyskowej lub linii pamięci podręcznej, prawie każdą tabelę z milionami lub miliardami rekordów można przeszukać w 3 lub 4 odczytach dyskowych, a górne jeden lub dwa poziomy zwykle pozostają na stałe zapamiętane w pamięci RAM, co sprawia, że ​​większość wyszukiwań jest w praktyce znacznie tańsza.

Drzewa B+ i drzewa B*,

Praktycznie żadna baza danych produkcyjnych nie wykorzystuje prostego drzewa B; niemal wszystkie używają drzewa B+, z powodu różnicy: wewnętrzne węzły w drzewie B+ przechowują kopie kluczy wyłącznie do kierowania wyszukiwaniami, podczas gdy cała rzeczywista zawartość znajduje się w liściach, a liście są połączone w łańcuch. Ten łańcuch przekształca zapytanie o zakres sortowany — "daj mi wszystkie wiersze między X i Y" — w pojedynczą desencję drzewa, po której następuje szybki ruch bokiem wzdłuż połączonych liści, zamiast wielokrotnych pełnych przeszukań drzewa. Drzewo B* idzie o krok dalej i opóźnia podział. Gdy węzeł przepełnia się, najpierw próbuje rozłożyć klucze z sąsiadem, dzieląc się tylko wtedy, gdy oba sąsiednie węzły również są pełne, a następnie dzieli dwa pełne węzły na trzy prawie pełne węzły zamiast dwóch częściowo pełnych — utrzymując węzły bardziej pełne (około 2/3 zamiast 1/2) kosztem bardziej złożonego wstawiania.

Frequently asked questions

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz B-Trees i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.