Odkrywcy lub wynalazcy | Rudolf Bayer , Edward M. McCreight |
---|---|
Data odkrycia | 1972 |
Powiązany problem | Struktura danych |
Struktura danych | Ukorzenione drzewo |
Najgorszy przypadek | , , |
---|---|
Średni | , , |
Najgorszy przypadek | |
---|---|
Średni |
W informatyce , o drzewo B (zwany także B-tree przez analogię do angielskiego terminu „ B-tree ”) to struktura danych w zrównoważonym drzewie . Drzewa B są głównie implementowane w mechanizmach zarządzania bazami danych i systemem plików . Przechowują dane w posortowanej formie i umożliwiają wykonywanie operacji wstawiania i usuwania w zawsze logarytmicznym czasie.
Zasada jest taka, aby węzły nadrzędne miały więcej niż dwa węzły potomne: jest to uogólnienie drzewa wyszukiwania binarnego . Zasada ta minimalizuje rozmiar wału i zmniejsza liczbę operacji wyważania. Ponadto drzewo B wyrasta z korzenia, w przeciwieństwie do binarnego drzewa badawczego, które wyrasta z liści.
Twórca drzew B, Rudolf Bayer , nie wyjaśnił znaczenia litery „B”. Najczęstszym wyjaśnieniem jest to, że B odpowiada angielskiemu terminowi „ zrównoważony ” (w języku francuskim: „zrównoważony”). Mogło jednak również pochodzić od „Bayer”, czyli od nazwiska twórcy, lub od „Boeing”, od nazwy firmy, dla której twórca pracował ( Boeing Scientific Research Labs ).
Drzewa B zostały wynalezione w 1970 roku przez Rudolfa Bayera i Edwarda M. McCreighta w laboratoriach badawczych Boeinga . Celem było umożliwienie zarządzania stronami indeksowymi plików danych, biorąc pod uwagę, że objętość indeksów może być tak duża, że tylko ułamek stron można załadować do pamięci RAM. Pierwszy artykuł opisujący mechanizm drzew B został napisany w lipcu i opublikowany wListopad 1970.
Oznaczone drzewo to drzewo (w sensie komputerowym terminu) tak, że każdy węzeł jest związany z etykietą lub klawisza (lub kilku etykiet klawiszy lub w przypadku drzew B) pochodzą z danego zbioru. Zatem formalnie oznaczone drzewo jest parą utworzoną z ukierunkowanego, acyklicznego i połączonego grafu oraz z funkcji etykietowania drzewa, która przypisuje każdemu węzłowi etykietę lub klucz. Wśród oznaczonych drzew drzewo B ma kilka dodatkowych, specyficznych właściwości.
Niech L i U będą dwiema naturalnymi liczbami całkowitymi niezerowymi takimi, że L ≤ U. Generalnie definiujemy drzewo LU B w następujący sposób: każdy węzeł, oprócz korzenia, ma co najmniej L - 1 kluczy (zwanych również elementami), maksymalna U - 1 kluczy i na większości dzieci u. Dla każdego węzła wewnętrznego - węzła, który nie jest liściem - liczba dzieci jest zawsze równa liczbie kluczy powiększonej o jeden. Jeśli n jest liczbą dzieci, to mówimy o n- węzeł. Drzewo LU zawiera tylko n-węzły o L ≤ n ≤ U. Często wybieramy konfigurację L = t i U = 2 × t: t nazywamy minimalnym stopniem drzewa B.
Ponadto konstrukcja wałów B zapewnia, że wałek B jest zawsze wyważony . Każdy klucz węzła wewnętrznego jest w rzeczywistości ograniczeniem, które odróżnia poddrzewa tego węzła. Na przykład, jeśli węzeł ma 3 dzieci - które stanowią odpowiednie korzenie trzech poddrzewa: lewego poddrzewa, środkowego poddrzewa i prawego poddrzewa - to ma 2 klucze oznaczone c 1 i c 2, które ograniczają klucze każdego poddrzewa: klucze lewego poddrzewa będą mniejsze niż c 1 ; klucze środkowego poddrzewa będą znajdować się między c 1 a c 2 ; klucze prawego poddrzewa będą większe niż c 2 .
Drzewo B jest implementowane przez zrootowane drzewo. Węzeł jest oznaczony przez:
Ponadto drzewo B spełnia następujące właściwości:
W większości przypadków konfiguracja jest taka, że U = 2 L. Mówimy wtedy o drzewie B rzędu L.
Drzewo B rzędu t jest wtedy definiowane prościej przez drzewo, które spełnia następujące właściwości:
Jak zobaczymy później, wysokość drzewa B jest logarytmiczna w liczbie elementów. Zatem operacje wyszukiwania, wstawiania i usuwania mogą być realizowane w O (log n) w najgorszym przypadku, gdzie n jest liczbą elementów.
Wyszukiwanie odbywa się w taki sam sposób, jak w drzewie wyszukiwania binarnego . Zaczynając od korzenia, przechodzimy przez drzewo rekurencyjnie; w każdym węźle wybieramy poddrzewo potomne, którego klucze znajdują się między tymi samymi granicami, co klucze klucza poszukiwanego za pomocą wyszukiwania dychotomicznego.
Pseudo kod fonction Rechercher(noeud, x): i = 0 tant que i < noeud.taille et x > noeud.cles[i]: i += 1 si noeud.feuille: retourner x == noeud.cles[i] sinon: si x == noeud.cles[i]: retourner Vrai sinon si i == noeud.taille et x > noeud.cles[noeud.taille - 1]: retourner Rechercher(noeud.branches[noeud.taille], x) sinon: retourner Rechercher(noeud.branches[i], x)W wielu implementacjach równość ( ) między elementami jest zastępowana przez równoważność ( ). Dlatego należy uważać, aby używać typów danych, w których dwa równoważne elementy są uważane za równe.
Wstawienie wymaga najpierw znalezienia węzła, w którym należy wstawić nowy klucz, i wstawienia go. Reszta odbywa się rekurencyjnie, w zależności od tego, czy węzeł ma zbyt wiele kluczy: jeśli ma akceptowalną liczbę kluczy, nic się nie dzieje; w przeciwnym razie przekształcamy go w dwa węzły, z których każdy ma minimalną liczbę kluczy, a następnie ustawiamy środkowy klawisz „w górę”, który jest następnie wstawiany do węzła nadrzędnego. Ten ostatni może nagle zakończyć się nadmierną liczbą wątków; proces jest kontynuowany w ten sposób, aż do osiągnięcia korzenia. Jeśli ten jeden musi zostać podzielony, powoduje się, że „idź w górę” środkowy klucz w nowym katalogu głównym, który wygeneruje jako węzły potomne dwa węzły utworzone, zaczynając od starego, tak jak w poprzednim kroku. Aby operacja była możliwa, zauważamy, że U ≥ 2 L; w przeciwnym razie nowe węzły nie będą miały wystarczającej liczby kluczy.
Wariant polega na prewencyjnym rozstrzeliwaniu każdego „pełnego” węzła (posiadającego maksymalną liczbę kluczy) napotkanego podczas poszukiwania węzła, w którym nastąpi wstawienie. W ten sposób unikamy cofania się w górę drzewa, ponieważ zapewniamy, że ojciec węzła, który ma zostać podzielony na dwie części, może pomieścić dodatkowy klucz. Odpowiednik to niewielki wzrost średniej wysokości drzewa.
Pseudo kod fonction Inserer(x,c) n = nombre de clefs du noeud x Soit i tel que x.clef[i] > c ou i >= n Si x est une feuille : Inserer c dans x.clef a la i-ieme place Sinon: Si x.fils[i] est complet: Scinder x.fils[i] Si c > x.clef[i]: i := i+1 FinSi FinSi Inserer(x.fils[i],c) FinSi FinFonctionNajpierw musimy znaleźć klucz, aby go usunąć i usunąć z węzła, który go zawiera.
Szczególnie po usunięciu drzewo można wyważyć. Ta operacja polega na sprawiedliwym rozłożeniu wartości w różnych węzłach drzewa i przywróceniu minimalnych właściwości wypełnienia węzłów.
Równowaga zaczyna się na poziomie liści i postępuje w kierunku korzenia, aż do korzenia. Redystrybucja obejmuje przeniesienie elementu z sąsiedniego węzła, który ma wystarczające wartości, do węzła, w którym ich brakuje. Ta redystrybucja nazywa się rotacją . Jeśli żaden sąsiad nie może podać wartości bez znajdowania się poniżej limitu, wadliwy węzeł musi zostać scalony z sąsiadem. Ta operacja powoduje utratę separatora w węźle nadrzędnym, ten może wtedy być deficytowy i musi zostać zrównoważony. Fuzja i redystrybucja rozprzestrzeniają się aż do korzenia, jedynego elementu, w którym tolerowany jest niedobór wartości.
Prosty algorytm równoważenia składa się z:
Obrót wycięcia w lewo między dwoma sąsiednimi węzłami jest wykonywany w
Tego rodzaju operacji można również użyć do skompresowania drzewa: drzewo przeznaczone tylko do odczytu można opróżnić z maksymalnie niewykorzystanych gniazd pamięci, wypełniając jak najmniej węzłów.
Niech będzie liczbą kluczy zawartych w drzewie B.Wysokość drzewa spełnia nierówność:
DemonstracjaKorzeń drzewa zawiera co najmniej 1 węzeł, więc ma co najmniej 2 dzieci. Węzły o głębokości co najmniej 1 zawierają co najmniej klucze L-1 i L dzieci. Za pomocą indukcji pokazujemy bowiem, że poziom drzewa, czyli zbiór węzłów głębokości , zawiera co najmniej węzły, a zatem co najmniej klucze. Dlatego sprawdzana jest łączna liczba kluczy w drzewie:
Więc i .
Szyb B + Tree (en) różni się nieco od drzewa B tym, że wszystkie dane są przechowywane tylko w liściu i są ze sobą połączone.
Istnieją również inne warianty, takie jak drzewo B * (en) .