Z Wikipedii

B-drzewa to struktury danych używane przede wszystkim w systemach baz danych. Chociaż tak naprawdę najpopularniejsze w zastosowaniach bazo-danowych i systemach plików (np. NTFS) są B+drzewa, które są szczególnym przypadkiem B-drzew, przechowującym dane tylko w liściach.

Głównym pomysłem zastosowanym w B-drzewach jest struktura wewnętrznego węzła. Każdy węzeł może posiadać od n do 2 * n + 1 węzłów potomnych, gdzie n to rząd B-drzewa. Wyjątkiem jest korzeń, który może posiadać od 0 do 2 * n + 1 węzłów potomnych. Dzięki temu B-drzewa nie wymagają częstego wyważania, w przeciwieństwie do drzew AVL.

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

Każdy wewnętrzny węzeł drzewa posiada wartości rozdzielające (najczęściej są to po prostu stopnie wierzchołka), 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 mniejsze 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). Naprawdę duża liczba n (np. 1024) jest kluczem w wydajności B-drzew ponieważ wysokość drzewa dla ogromnej ilości węzłów liczonej w milionach lub miliardach będzie bardzo mała. Np. dla n=1024 w B-drzewie o wysokości 2 można umieścić około miliona węzłów.

   

Zobacz galerię na Wikimedia Commons:
B-drzewo

Zobacz też: drzewo (informatyka)