B-drzewo

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
B-tree-definition.png

B-drzewodrzewiasta struktura danych, przechowująca klucze w pewnym porządku i powiązane z nimi dane, używana przede wszystkim w systemach baz danych. Popularniejsze w zastosowaniach bazodanowych i systemach plikówB+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 M do 2 * M + 1 węzłów potomnych, gdzie M to rząd B-drzewa; wyjątkiem jest korzeń, który może posiadać od 0 do 2 * M + 1 węzłów potomnych. Te założenia gwarantują, że wysokość drzewa zawierającego n kluczy będzie niska, rzędu \log_M{n}, co też powoduje, że asymptotyczna złożoność czasowa operacji podstawowych: wyszukiwania, wstawiania i kasowania kluczy jest rzędu O(\log_M{n}).

Niska wysokość drzewa powoduje, że liczba węzłów, które trzeba odczytać bądź zapisać, jest niewielka. W praktycznych zastosowaniach, w których informacje przechowywane są na dyskach twardych bądź płytach CD/DVD ma to fundamentalne znaczenie, bowiem czasy dostępu do tych urządzeń są dużo większe niż do pamięci wewnętrznej komputera i dominują w całkowitym czasie wykonywania operacji na danych (czasy dostępu do pamięci komputera rzędu mikro- lub setek nanosekund, natomiast do współczesnych dysków twardych to kilka milisekund - czyli 3-4 rzędy wielkości więcej). Z kolei zlokalizowanie odpowiedniego klucza bądź potomka w węźle wczytanym do pamięci wewnętrznej jest dużo szybsze, nawet jeśli rząd drzewa jest duży.

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

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 M tzn. każdy z węzłów zawiera od M do 2M kluczy (wyjątkiem jest korzeń, który może zawierać od 1 do 2M) 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 M (np. 1024) jest kluczowa 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 M=1024 w B-drzewie o wysokości 2 można umieścić około miliona węzłów.

Commons in image icon.svg

Zobacz też[edytuj | edytuj kod]