Tekst źródłowy strony B-drzewo

[[Plik:B-tree-definition.png|right|400px]]
'''B-drzewo''' – [[drzewo (informatyka)|drzewiasta]] [[struktura danych]], przechowująca klucze w pewnym porządku i powiązane z nimi dane, używana przede wszystkim w systemach [[baza danych|baz danych]].

Głównym pomysłem zastosowanym w B-drzewach jest struktura wewnętrznego węzła. Każdy węzeł może posiadać od <math>M + 1</math> do <math>2 \cdot M + 1</math> węzłów potomnych, gdzie <math>M</math> to '''rząd''' B-drzewa; wyjątkiem jest korzeń, który może posiadać od <math>0</math> do <math>2 \cdot M + 1</math> węzłów potomnych. Te założenia gwarantują, że wysokość drzewa zawierającego <math>n</math> kluczy będzie niska, rzędu <math>\log_M{n},</math> co też powoduje, że [[asymptotyczne tempo wzrostu|asymptotyczna]] [[złożoność obliczeniowa|złożoność czasowa]] operacji podstawowych: wyszukiwania, wstawiania i kasowania kluczy jest rzędu <math>O(\log_M{n}).</math>

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 [[dysk twardy|dyskach twardych]] bądź płytach [[płyta kompaktowa|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.

== B+drzewo ==
Popularniejsze w zastosowaniach [[baza danych|bazodanowych]] i [[system plików|systemach plików]] są '''B+drzewa''', które są szczególnym przypadkiem B-drzew, przechowującym dane tylko w liściach.

== 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 '''''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.

== Zobacz też ==
{{commonscat|B-Trees}}
* [[2-3 drzewo]]
* [[drzewo binarne]]

== Linki zewnętrzne ==

* [https://people.ksp.sk/~kuko/gnarley-trees/Btree.html Wizualizacja B-drzewa]

[[Kategoria:Drzewa (informatyka)]]