Jak wprowadzać rekordy za pomocą kluczy do początkowo pustego drzewa B +?

Pokaż wynik wpisywania rekordów kluczami w kolejności (1, 2, 3, 4, 5) do początkowo pustego drzewa B + - rzędu rzędu m = 3. W przypadku przepełnienia podziel węzeł i nie rozpowszechniaj ponownie klucze do sąsiadów. Czy można wprowadzić rekordy za pomocą kluczy w innej kolejności, aby mieć drzewo o mniejszej wysokości?

Z relacyjnych części wewnętrznych DBMS, rozdział 5: Dynamiczne organizacje o strukturze drzewa, s. 50

Nie jestem w tym dobry, ale próbowałem zrobić ≤ po lewej i> po prawej:

Do wstawienia 1,2:

Następnie, o ile musimy podzielić węzeł i nie redystrybuować kluczy do sąsiadów (rozumiem to jako syn-węzły), wstawiłem tylko po prawej stronie komórki za pomocą 2:

I nadal robiłem to samo przy wstawianiu 5:

Ale to dość dziwne, nigdy nie widziałem takich pustych węzłów ... I nie wiem, czy szanuje niektóre bardzo podstawowe właściwości drzew B:

• każdy węzeł ma co najwyżej (m-1) klucze i co najmniej (⌈ (m / 2) ⌉-1) klucze, chyba że klucz może być pusty i zrozumiałbym go jako „wskaźnik”.

Pierwsza próba: błąd w zamówieniu ujawnił niejednoznaczne drzewo

Na początku źle zrozumiałem, czym było „zamówienie” (maksymalna liczba dzieci na węzeł). Pomyślałem więc, że węzeł może mieć trzy spacje (a zatem 4 dzieci. Tworzyłem drzewo rzędu 4, myślę:

Do wstawienia 1,2,3:

Wstawienie 4, o ile musimy podzielić węzeł, a nie ponownie dystrybuować klucze do sąsiadów (co wydaje się sprzeczne) Pozwoliłbym 1,2,3 i 4,5 na prawym liściu po 3:

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.