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ą...

Zagadnienia poruszane w tym artykule:

• BTree w bazach danych;
• Podstawowe założenia;
• Wyszukiwanie elementu w BTree;
• Wstawianie nowego elementu do BTree;
• Usuwanie elementu z BTree;

Artykuł pochodzi magazynu Programista nr 80 (1/2019). Jest to wydanie z kwietnia 2019 r. Szczegółowy spis treści: https://programistamag.pl/programista-1-2019-80/

Autorem artykułu jest Piotr Jastrzębski. Inżynier oprogramowania z jedenastoletnim stażem. Aktualnie pracuje nad rozproszoną bazą danych NoSQL o nazwie Scylla. Wcześniej rozwijał real-time trading system w londyńskim City oraz pracował nad systemem Android w firmie Google. Absolwent informatyki na Uniwersytecie Warszawskim.