(składnia)

Piotr Jastrzębski: BTree – jak działa i dlaczego nadaje się do baz danych

Programista 1/2019 (80) kwiecień 2019 [okładka]

BTree jest uporządkowaną strukturą danych podobną do zrównoważonego binarnego drzewa przeszukiwań. Podstawowa różnica polega na tym, że węzły w BTree mogą posiadać więcej niż dwoje dzieci. Drzewiasta forma sprawia, że podstawowe operacje, takie jak wstawianie, usuwanie i wyszukiwanie elementu, zajmują czas proporcjonalny do wysokości drzewa, czyli O(log(liczba elementów w strukturze)). Zwiększone rozgałęzienie BTree sprawia, że jego wysokość jest zdecydowanie mniejsza niż wysokość zrównoważonego binarnego drzewa przeszukiwań zawierającego te same elementy. Sprawia to, że – mimo tej samej klasy złożoności operacji na tych strukturach danych – BTree w wielu zastosowaniach, takich jak bazy danych czy systemy plików, charakteryzuje się znacząco większą wydajnością.