Indeks B+ Drzewa Bazowych Danych

Co czyni go drzewem B+, a nie tylko drzewem B?

Zwykłe drzewo B pozwala przechowywać parę klucz-wartość w dowolnym węźle, wewnętrznym lub liściowym, w momencie wprowadzenia klucza i gdy węzeł ma wystarczająco dużo miejsca. Drzewo B+ zmienia to zasady na dwa sposoby. Po pierwsze, węzły wewnętrzne przechowują jedynie kopie używanych kluczy do routingu; nigdy nie zawierają rzeczywistego ładunku rekordu. Druga sprawa to fakt, że każdy prawdziwy rekord, wraz z pełnym kluczem, znajduje się w węźle liściowym i tylko w węźlu liściowym. Podczas wprowadzania klucza drzewo zawsze przechodzi do węzła liściowego, aby go umieścić, a jeśli ten klucz również musi pojawić się w węźle wewnętrznym jako separator, to tylko kopia klucza podróżuje w górę, nie dane. Ta separacja ma praktyczny efekt: węzły wewnętrzne stają się znacznie mniejsze na każdy klucz, ponieważ nie zawierają ładunku, dzięki czemu więcej kluczy routingu może zmieścić się na pojedynczej stronie dyskowej lub bloku pamięci. Węższe i szersze drzewo oznacza mniej poziomów do zejścia przed dotarciem do węzła liściowego, a to z kolei oznacza mniej kosztownych losowych odczytów z dysku. W tradycyjnym drzewie B ładunek mieszany w węzłach wewnętrznych powiększa je i zmusza drzewo do bycia wyższym dla tej samej ilości danych. Drugą definiującą cechę, a tą, na której koncentruje się ten eksperyment, jest fakt, że węzły liściowe są połączone w uporządkowany kolejności kluczy, zwykle jako podwójnie połączona lista, dzięki czemu możliwe są skanowania w przód i w tył. Ten link jest niewidoczny w zwykłym drzewie B, ponieważ liście są izolowanymi martwymi końcami, a przejście od danych jednego liścia do następnego posortowanego liścia wymaga powrotu do wspólnego przodka i ponownego zejścia. W drzewie B+ ten wzrost nie jest potrzebny. Drzewo jest obniżane dokładnie raz, aby znaleźć pierwszy pasujący liść, a wszystko po nim to prosta wędrówka wzdłuż łańcucha. Spróbuj zbudować drzewo w tym laboratorium i zauważ, że niezależnie od tego, jak głęboko rośnie, liście zawsze pozostają ze sobą połączone w lewo do prawo w rosnącej kolejności.”]} pango-ignore: markdown, code, header, list, image, table, blockquote, h1, h2, h3, h4, h5, h6, ul, ol, dl, dt, dd, pre, code, abbr, acronym, sup, sub, cite, strong, b, i, u, em, var, dfn, kbd, samp, code, span, font, big, small, br, hr, blockquote, caption, figure, table, tbody, tfoot, thead, tr, th, td, col, column, abbr, acronym, cite, div, pre, code, bdo, bfrag, dfn, embed, haslayout, samp, sup, sub, var, input, button, select, textarea, iframe, details, summary, mark, dialog, term, svg, math, html, body, head, title, meta, link, style, script, abbr, cite, cite, small, area, audio, video, source, track, canvas, input, button, select, textarea, object, param, svg, iframe, details, summary, caption, figure, table, tbody, tfoot, thead, tr, th, td, col, column, abbr, cite, cite, small, area, audio, video, source, track, canvas, input, button, select, textarea, object, param, svg, iframe, details, summary

Dlaczego Lista Połączona Liśćmi Zmienia Wszystko dla Przebiegów Zakresowych

Rozważ zapytanie dotyczące wszystkich transakcji z datą znacznikową pomiędzy dwoma datami. W strukturze bez połączonych liści, zaspokojenie tego zapytania oznacza znalezienie pierwszego kwalifikującego klucza, a następnie wielokrotne zadawanie pytania drzewu: co jest następne? Każde z tych pytań może wymagać cofnięcia się w kierunku korzenia i powrotnego przemieszczenia się inną ścieżką, ponieważ kolejny klucz w kolejności nie musi być sąsiednim elementem w tym samym węźle. Dla zakresu obejmującego tysiące wierszy, to sumuje się do dużej liczby przebiegów drzewa, każdy z nich potencjalne losowe odczyty dyskowe. Drzewo B+ eliminuje prawie cały ten wysiłek. Bazą danych jest pojedyncze zejście w dół, aby znaleźć liść zawierający pierwszy klucz większy lub równy początkowi zakresu. Od tamtej chwili po prostu śledzi następnik liścia, czytając rekordy w kolejności posortowanej, aż osiągnie klucz przekraczający koniec zakresu. Każdy krok to tani ruch sekwencyjny do sąsiedniego liścia zamiast świeżej nawigacji drzewem. Na dyskach obrotowych miało to ogromne znaczenie, ponieważ odczyty sekwencyjne były znacznie szybsze niż losowe; na nowoczesnych pamięciach masowych różnica jest mniejsza, ale nadal realna, a redukcja pracy CPU (mniej porównań, mniej polowań na wskaźniki przez wewnętrzne węzły) pozostaje znacząca niezależnie od tego. Ten sam mechanizm przyspiesza pełne skanowanie indeksów i sortowane wyjście szerzej. Planer zapytań często chce dane w kolejności kluczy, aby zaspokoić klauzulę ORDER BY, aby zasilić połączenie scalające lub obliczyć agregację nad oknem wierszy. Zamiast oddzielnie sortować dane po pobraniu, silnik może po prostu przejść łańcuchem liści istniejącego indeksu i uzyskać posortowane wyjście zasadniczo za darmo. Dlatego właśnie funkcja łączenia liści nie jest szczegółem implementacyjnym; często jest to główny powód, dla którego drzewo B+ przewyższa zwykłe drzewo B- w rzeczywistych obciążeniach baz danych.”]} pablo.png

Dlaczego MySQL InnoDB i PostgreSQL Wybierają Drzewa B+},

Domyślny silnik przechowywania MySQL, InnoDB, buduje indeks klucza głównego jako drzewo B+, w którym same liście przechowują pełne dane wierszy, układ często nazywany indeksem zclustrowaniem. Każdy indeks pomocniczy w InnoDB jest również drzewem B+, ale jego liście przechowują wartości kolumn indeksowanych oraz odniesienie do klucza głównego, a nie pełny wiersz. W obu przypadkach struktura połączonych listów jest tym, co sprawia, że efektywne są predykaty zakresu, takie jak WHERE order_date BETWEEN X I Y: silnik znajduje początkowy list raz i płynie do przodu. PostgreSQL podejmuje powiązany, ale odmienny sposób. Jego domyślny typ indeksu, myląco nazwany metodą dostępu B-drzewa, w praktyce jest zaimplementowany jako drzewo B+ wewnętrznie, z liściami przenoszącymi dane połączonymi w kolejności posortowanej za pomocą wskaźników brata, ponownie aby wspierać efektywne skanowanie zakresu, skanowanie posortowane i nawet odwrotne skanowanie dla sortowania malejącego. Żaden z tych silników nie używa starszej, prostej struktury drzewa B do swoich codziennych indeksów, ponieważ produkcji dominują wyszukiwania punktowe połączone ze skanowaniami zakresu, a zaprojektowana na podstawie łączenia list dobrze sprawdza się w obu przypadkach. Istnieją również dodatkowe korzyści. Wewnętrzne węzły nie przechowują danych roboczych, więc dobrze się kompresują i mają tendencję do pozostawania w pamięci (bufor podręczny lub współdzielony bufor cache), dzięki czemu jedynym dyskowym dostępem często potrzebnym jest poziom liści. Pełne skanowanie tabeli, indeks-tylko skany, które całkowicie unikają dotykania podległej tabeli i operacje eksportu hurtowego opierają się na tej samej wężyście wędrownej po liście. Nawet rutynowe utrzymanie, takie jak ponowne tworzenie indeksu lub obliczanie statystyk, korzysta z możliwości przepływu przez posortowane dane bez wielokrotnego przeszukiwania drzewa. Ta kombinacja kompaktowego routingu węzłów i posortowanej łańcucha liści jest powodem, dla którego drzewo B+ a nie klasyczne drzewo B stało się domyślnym wyborem dla indeksów relacyjnych baz danych.

Wstawianie, Podziały i Utrzymywanie Łańcucha

Wstawianie do drzewa B+ rozpoczyna się podobnie jak w przypadku drzewa B: zejście od korzenia, porównywanie nowego klucza z kluczami separatorowymi w każdym węźle wewnętrznym, aż do osiągnięcia odpowiedniego liścia. Klucz i jego rekord są dodawane do tego liścia w uporządkowanej pozycji. Jeśli liść zawiera teraz więcej wpisów niż pozwala na to jego pojemność, dzieli się na dwa liście, z których każdy przechowuje około połowę wpisów. W tym przypadku drzewo B+ odbiega od klasycznego algorytmu ważnym sposobem. Podczas gdy w zwykłym drzewie B węzeł wewnętrzny dzieli się, środek klucza jest przenoszony do rodzica i usuwany z dzieci, ponieważ klucze są unikalne dla jednego miejsca w drzewie. W drzewie B+ podczas podziału liścia najmniejszy klucz nowego prawego liścia jest kopiowany (nie przenoszony) do rodzica jako separator; klucz nadal fizycznie pozostaje w liście obok swoich danych, ponieważ liście muszą przechowywać każdy klucz z jego rekordem. Przenosi się tylko wtedy, gdy węzeł wewnętrzny dzieli się, kiedy klucz naprawdę przemieszcza się bez pozostawiania za sobą, ponieważ węzły wewnętrzne nie przechowują własnych danych do zachowania. Tak samo ważne jest, aby podział aktualizował wskaźniki listy powiązanych, aby łańcuch pozostał niesprzeczony: poprzedni wskaźnik nowego prawego liścia ustawiany jest na oryginalny liść, następny wskaźnik oryginalnego liścia przekierowywany jest do nowego liścia, a następny wskaźnik nowego liścia przejmuje to, na co wcześniej wskazywał oryginalny liść. Pominięcie tego kroku spowodowałoby ciche przerwanie skanów zakresowych przecinających punkt podziału, nawet jeśli struktura routingu powyżej liści wyglądałaby nadal prawidłowo. Jeśli podział rozprzestrzenia się w górę i nawet korzeń dzieli się, tworzony jest nowy korzeń przechowujący pojedynczy klucz separatorowy, a drzewo rośnie o jeden poziom wyżej, ale poziom liści i jego łańcuch pozostają niesprzeczonym, posortowanym ciągiem w całym.}$]}$$${

Usuwanie, Reorganizacja i Realne Kompromisy

Usunięcie klucza przebiega zgodnie z tym samym początkowym ścieżką: zejście do liścia zawierającego go i usunięcie wpisu. Jeśli liść po usunięciu nadal ma co najmniej minimalną wymagany liczbę wpisów, nic więcej nie musi się wydarzyć strukturalnie, choć separator klucza wyższego w drzewie może teraz być nieco przestarzały; większość implementacji toleruje to, ponieważ nadal prawidłowo kieruje wyszukiwania, o ile pozostaje spójny z granicą między potomkami. Jeśli usunięcie pozostawia liść niedobór wpisów, drzewo próbuje pożyczyć wolny wpis od sąsiadującego liścia pobocznego, dostosowując separator klucza rodzica do odpowiadającego wartości. Gdy pożyczanie nie jest możliwe, ponieważ sąsiedni liść również osiągnął minimalną wartość, dwa liście są łączone w jeden, a odpowiedni separator klucza jest usuwany z rodzica. Kluczowe jest to, że scalanie dwóch liści oznacza również łączenie ich pozycji w liście powiązanej; wskazany następny wskaźnik przeżywającego liścia musi zostać zaktualizowany, aby ominąć odrzucany liść, a poprzedni wskaźnik następnego liścia musi wskazywać z powrotem na przeżywającego liścia. Tak jak w przypadku podziałów, ta księgowość jest łatwa do popełnienia nieprawidłowo w implementacji od podstaw, a uszkodzony wskaźnik może spowodować, że skan zakresu będzie cicho pomijać dane lub wpadać w pętlę, nawet jeśli wyszukiwanie punktowe przez drzewo nadal się powiedzie. Bazy danych akceptują ten kompromis poprzez pewne duplikowanie przechowywania kluczy, ponieważ separatorów kluczy w węzłach wewnętrznych są kopiami kluczy, które również znajdują się w liściach, a każdy liść posiada dwa dodatkowe wskaźniki dla swoich sąsiadów. W zamian otrzymują prawie stałą czasową dostępność do następnego lub poprzedniego rekordu w kolejności posortowanej, odporne wsparcie zarówno dla równości, jak i predykatów zakresu poprzez tę samą strukturę oraz wewnętrzne węzły wystarczająco kompaktowe, aby większość drzewa mieściła się w pamięci. Jest to kompromis, który każdy silnik baz danych produkcyjnych uznał za wart, dlatego, mimo nazwy rodziny, to B+ drzewo, a nie oryginalne B-drzewo, wykonuje rzeczywistą pracę w indeksie, którego pytasz każdego dnia.

Często zadawane pytania

Wypróbuj na żywo

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