Przed zrozumieniem drzewo B I Drzewo B+ różnice, powinniśmy znać drzewo B i drzewo B+ osobno.

Co to jest drzewo B?

drzewo B jest drzewem samorównoważącym i jest drzewem m-drogowym, gdzie m określa porządek drzewa. Bdrzewo jest uogólnieniem Drzewo wyszukiwania binarnego w którym węzeł może mieć więcej niż jeden klucz i więcej niż dwoje dzieci, w zależności od wartości M . W drzewie B dane są określone w posortowanej kolejności, z niższymi wartościami w lewym poddrzewie i wyższymi wartościami w prawym poddrzewie.

gimp usuń znak wodny

Właściwości drzewa B

Poniżej przedstawiono właściwości drzewa B:

• W drzewie B wszystkie węzły liściowe muszą znajdować się na tym samym poziomie, natomiast w przypadku drzewa binarnego węzły liściowe mogą znajdować się na różnych poziomach.

Rozumiemy tę właściwość na przykładzie.

W powyższym drzewie wszystkie węzły liści nie są na tym samym poziomie, ale mają najwięcej dwójki dzieci. Można zatem powiedzieć, że powyższe drzewo jest a drzewo binarne ale nie drzewo B.

• Jeśli Btree ma rząd m, wówczas każdy węzeł może mieć maksymalnie M W przypadku minimalnych dzieci węzły liściowe mają zero dzieci, węzeł główny ma dwójkę dzieci, a węzły wewnętrzne mają pułap m/2.
• Każdy węzeł może mieć maksymalnie (m-1) kluczy. Na przykład, jeśli wartość m wynosi 5, wówczas maksymalna wartość kluczy wynosi 4.
• Węzeł główny ma co najmniej jeden klucz, podczas gdy wszystkie pozostałe węzły z wyjątkiem węzła głównego mają (sufit m/2 minus - 1) minimalną liczbę kluczy.
• Jeśli dokonamy wstawienia w drzewie B, wówczas węzeł jest zawsze wstawiany w węźle liścia.

Załóżmy, że chcemy utworzyć drzewo B rzędu 3, wstawiając wartości od 1 do 10.

Krok 1: Najpierw tworzymy węzeł z 1 wartością, jak pokazano poniżej:

Krok 2: Następnym elementem jest liczba 2, która następuje po liczbie 1, jak pokazano poniżej:

Krok 3: Następny element to 3 i jest wstawiany po 2, jak pokazano poniżej:

Ponieważ wiemy, że każdy węzeł może mieć maksymalnie 2 klucze, dlatego podzielimy ten węzeł przez środkowy element. Środkowy element ma wartość 2, więc przesuwa się do swojego rodzica. Węzeł 2 nie ma żadnego rodzica, więc stanie się węzłem głównym, jak pokazano poniżej:

Krok 4: Następnym elementem jest 4. Ponieważ 4 jest większe niż 2 i 3, zostanie ono dodane po 3, jak pokazano poniżej:

Krok 5: Następnym elementem jest 5. Ponieważ 5 jest większe od 2, 3 i 4, zostanie ono dodane po 4, jak pokazano poniżej:

Ponieważ wiemy, że każdy węzeł może mieć maksymalnie 2 klucze, dlatego podzielimy ten węzeł przez środkowy element. Środkowy element ma wartość 4, więc przesuwa się do swojego rodzica. Rodziciem jest węzeł 2; dlatego 4 zostanie dodane po 2, jak pokazano poniżej:

Krok 6: Następnym elementem jest 6. Ponieważ 6 jest większe niż 2, 4 i 5, więc 6 pojawi się po 5, jak pokazano poniżej:

Krok 7: Następnym elementem jest 7. Ponieważ 7 jest większe niż 2, 4, 5 i 6, więc 7 pojawi się po 6, jak pokazano poniżej:

Ponieważ wiemy, że każdy węzeł może mieć maksymalnie 2 klucze, dlatego podzielimy ten węzeł przez środkowy element. Środkowy element to 6, więc przesuwa się do swojego rodzica, jak pokazano poniżej:

Ale 6 nie można dodać po 4, ponieważ węzeł może mieć maksymalnie 2 klucze, więc podzielimy ten węzeł przez środkowy element. Środkowy element ma wartość 4, więc przesuwa się do swojego rodzica. Ponieważ węzeł 4 nie ma żadnego rodzica, węzeł 4 stanie się węzłem głównym, jak pokazano poniżej:

Co to jest drzewo B+?

The Drzewo B+ jest również znane jako zaawansowane drzewo samobalansujące, ponieważ każda ścieżka od korzenia drzewa do liścia drzewa ma tę samą długość. Tutaj ta sama długość oznacza, że ​​wszystkie węzły liściowe występują na tym samym poziomie. Nie będzie tak, że część węzłów liściowych pojawi się na poziomie trzecim, a część na drugim.

Indeks drzewa B+ jest uważany za indeks wielopoziomowy, ale struktura drzewa B+ nie jest podobna do plików sekwencyjnych indeksu wielopoziomowego.

Dlaczego używa się drzewa B+?

Drzewo B+ służy do bardzo wydajnego przechowywania rekordów poprzez przechowywanie rekordów w sposób indeksowany przy użyciu indeksowanej struktury drzewa B+. Dzięki wielopoziomowemu indeksowaniu dostęp do danych staje się szybszy i łatwiejszy.

Struktura węzła drzewa B+

Struktura węzłów drzewa B+ zawiera wskaźniki i wartości kluczy pokazane na poniższym rysunku:

Jak możemy zaobserwować w powyższej strukturze węzłów drzewa B+, zawiera ona n-1 wartości kluczy (k₁do k_n-1) i n wskaźników (s₁szczyt_N).

Wartości kluczy wyszukiwania umieszczone w węźle są przechowywane w posortowanej kolejności. Zatem, jeśli IIJ.

Ograniczenia dotyczące różnych typów węzłów

Niech „b” będzie porządkiem drzewa B+.

Węzeł inny niż liść

porównanie w Javie

Niech „m” oznacza liczbę dzieci węzła, wówczas relację pomiędzy porządkiem drzewa a liczbą dzieci można przedstawić jako:

Niech k reprezentuje wartości klucza wyszukiwania. Relację pomiędzy kolejnością drzewa a kluczem wyszukiwania można przedstawić jako:

Ponieważ wiemy, że liczba wskaźników jest równa wartościom klucza wyszukiwania plus 1, więc matematycznie można to zapisać jako:

Liczba wskaźników (lub dzieci) = liczba kluczy wyszukiwania + 1

Zatem maksymalna liczba wskaźników będzie wynosić „b”, a minimalna liczba wskaźników będzie funkcją górną b/2.

Węzeł liścia

Węzeł liścia to węzeł występujący na ostatnim poziomie drzewa B+, a każdy węzeł liścia używa tylko jednego wskaźnika do łączenia się ze sobą w celu zapewnienia sekwencyjnego dostępu na poziomie liścia.

W węźle liścia maksymalna liczba dzieci wynosi:

Maksymalna liczba kluczy wyszukiwania wynosi:

Węzeł główny

Maksymalna liczba dzieci w przypadku węzła głównego wynosi: b

Minimalna liczba dzieci to: 2

Przypadki specjalne w drzewie B+

Przypadek 1: Jeśli węzeł główny jest jedynym węzłem w drzewie. W tym przypadku węzeł główny staje się węzłem liścia.

W tym przypadku maksymalna liczba dzieci wynosi 1, czyli sam węzeł główny, natomiast minimalna liczba dzieci wynosi b-1, czyli jest taka sama jak węzeł liścia.

Reprezentacja węzła liścia w drzewie B+

Na powyższym rysunku „.” reprezentuje wskaźnik, podczas gdy 10, 20 i 30 to wartości kluczowe. Wskaźnik zawiera adres, pod którym przechowywana jest wartość klucza, jak pokazano na powyższym rysunku.

Przykład drzewa B+

Na powyższym rysunku węzeł zawiera trzy wartości kluczowe, tj. 9, 16 i 25. Wskaźnik pojawiający się przed 9 zawiera kluczowe wartości mniejsze niż 9 reprezentowane przez k_I. Wskaźnik pojawiający się przed liczbą 16 zawiera wartości kluczy większe lub równe 9, ale mniejsze niż 16 reprezentowane przez kj. Wskaźnik pojawiający się przed liczbą 25 zawiera wartości klucza większe lub równe 16, ale mniejsze niż 25 reprezentowane przez k_N.

Różnice pomiędzy drzewem B i drzewem B+

Poniżej przedstawiono różnice między drzewem B i drzewem B+: