Myślę, że masz stronę do góry nogami. Kiedy węzeł pęka nie tworzyć więcej węzłów w dół hierarchii (węzły syn w swojej nomenklaturze). Zamiast tego tworzy więcej w górę , w kierunku korzenia. Jak mówi książka
Zauważ, że wzrost znajduje się na szczycie drzewa, i jest to nieodłączna cecha drzewa B, aby zapewnić ważne właściwości, że zawsze ma wszystkie liście na tym samym poziomie, a każdy węzeł inny niż korzeń jest co najmniej 50% zapełnienia.
(Mój nacisk.)
Z połączonego ebooka:
Definicja 5.1 AB – drzewo rzędu m (m ≥ 3) ... każdy węzeł zawiera co najwyżej m - 1 klucze
Ćwiczenie dotyczy m = 3, więc maksymalnie 2 klucze na węzeł.
Pierwsze dwa klucze są łatwe - przechodzą na pierwszą stronę:
A:[1,2]
Użyję sztuki ASCII. Oznaczę każdą stronę w kolejności, w jakiej zostały utworzone, i pokażę klucze / wskaźniki na stronie. Zatem strona P zawierająca kluczowe wartości k1 i k2 będzie P:[k1,k2].
Teraz pojawia się klucz 3. Zgodnie z sekcją 5.2.1 ... Wstawianie, pierwszym zadaniem jest wyszukiwanie. To określa, że klucz 3 powinien znajdować się na stronie A - jedynej, którą mamy. Ponadto „jeśli [ten węzeł] jest pełny, zostanie on podzielony na dwa węzły.” Strona jest pełna, więc musi się podzielić. Teraz mamy
A:[1,2] B:[3, ]
Ale to nie jest drzewo! Jak mówi książka:
wskaźnik [do nowego węzła] .. dodaje się do ks węzła .. [tym bieżącego węzła] Powtarzając operację wstawiania w tym węźle [czyli węzła ks]. Ten proces podziału i przenoszenia może być kontynuowany, jeśli to konieczne, aż do katalogu głównego, a jeśli trzeba go podzielić, zostanie utworzony nowy węzeł główny.
(Nacisk na pokazanie przetwarzania trwa w górę drzewa w kierunku korzenia, a nie w kierunku liści.)
Musimy więc umieścić wskaźnik na nowej stronie (B) w ojcu bieżącej strony (A). Musi istnieć nowy węzeł główny:
C:[2,3]
/ \
A:[1,2] B:[3, ]
Mam wskaźniki na stronach innych niż liścia wskazujące najwyższą wartość w węźle potomnym (synu). Twój link może robić to inaczej, ale wynik będzie równoważny.
Nadchodzi kluczowa wartość 4; zgodnie z algorytmem szukamy, na której stronie powinien on być. Powinna to być strona B. Jest na to miejsce, więc aktualizujemy tę stronę i wskaźnik na stronie C:
C:[2,4]
/ \
A:[1,2] B:[3,4]
Następnie wstawiamy klucz 5. Powinien przejść na stronę B, ale jest pełny. Dlatego dzieli się
C:[2,4]
/ \
A:[1,2] B:[3,4] D:[5, ]
Musimy zaktualizować węzeł nadrzędny. Jest również pełny, więc dzieli:
C:[2,4] E:[5, ]
/ \ \
A:[1,2] B:[3,4] D:[5, ]
Podział propaguje się i tworzy się nowy węzeł główny:
F:[4,5]
/ \
C:[2,4] E:[5, ]
/ \ \
A:[1,2] B:[3,4] D:[5, ]
Rosnące w górę drzewo utrzymuje identyczną głębokość w każdej gałęzi. Jest to ważne dla przewidywalnej wydajności. (Niektórzy twierdzą, że B w B-Tree oznacza „zrównoważony” z tego właśnie powodu.)
Co do drugiej części - „Czy można wprowadzić rekordy za pomocą kluczy w innej kolejności, aby mieć drzewo o mniejszej wysokości?” Z 5 kluczami i dwoma kluczami na węzeł potrzebujemy co najmniej 3 węzłów liści, aby pomieścić wszystkie wartości, a wysokość 3, aby utworzyć drzewo. Więc mój układ jest optymalny dla danych, sekwencji i algorytmu.
Książka używa zupełnie innego układu wskaźników niż to, którego używam, i innego układu podziału strony. Będzie to znaczące, prowadzące do stron w całości. To, że na stronie 42 znajduje się sekcja o nazwie „Ładowanie danych”, która pokazuje, w jaki sposób można uzyskać pełniejsze strony po wczytaniu sekwencji klawiszy, wspiera moje przeczucie. Mam jednak nadzieję, że podałem ci wystarczającą liczbę wskazówek i będziesz w stanie użyć struktury wskaźnika książki, aby samemu to wypracować.
Natknąłem się na tę interaktywną symulację wzrostu B-drzewa.
