B-drzewo

Z Wikipedii

Masz nowe wiadomości (różnica z poprzednią wersją).

B-drzewa to struktury danych używane przede wszystkim w systemach baz danych.

Głównym pomysłem zastosowanym w B-drzewach jest struktura wewnętrznego węzła. Każdy węzeł wewnętrzny może posiadać zmienną liczbę węzłów potomnych z zadanego zakresu. Dzięki temu B-drzewa nie wymagają częstego wyważania, w przeciwieństwie do drzew AVL. Dolne i górne ograniczenia na liczbę węzłów potomnych nie są stałe i zależą od implementacji.

[edytuj] Struktura węzła wewnętrznego

Każdy wewnętrzny węzeł drzewa posiada wartości rozdzielące (najczęściej są to po prostu wartości drzewa), które wyznaczają jego poddrzewa. Przykładowo, jeśli węzeł wewnętrzny posiada 3 węzły (lub poddrzewa) potomne, to musi posiadać też 2 wartości rozdzielające A1 i A2. Wszystkie wartości miejsze lub równe A1 znajdują się w poddrzewie po lewej stronie, wartości pomiędzy A1 i A2 znajdują się w środkowym poddrzewie, z kolei wartości większe od A2 są umiejscowione w prawym poddrzewie.

Każdej informacji w B drzewie jest przyporządkowany unikatowy klucz względem którego całe drzewo zostało posortowane (dokładniej mówiąc to sortowanie odbywa się już w trakcie tworzenia drzewa, także od samego początku jest ono uporządkowane).

Każde B drzewo jest rzędu n tzn. każdy z węzłów zawiera od n do 2n kluczy (wyjątkiem jest korzeń, który może zawierać od 1 do 2n) i dlatego węzły są zawsze przynajmniej na wpół wypełnione kluczami. Węzeł posiadający k kluczy zawsze zawiera k+1 wskaźników (potomków - dzieci).