Co oznacza nazwa B-drzewo i jak jest zbudowane?

Drzewo B to zrównoważone drzewo wyszukiwań, zoptymalizowane do pracy z dużymi ilościami danych przechowywanych na zewnętrznych nośnikach (np. na dysku). Nazwa "drzewo B" pochodzi od angielskiego "Balanced" (zrównoważone) lub "Bayer" – nazwiska jednego z wynalazców.

Główne cechy drzewa B:

• Każdy węzeł zawiera kilka kluczy i wskaźników na węzły potomne, co pozwala zmniejszyć wysokość drzewa.
• Wszystkie liście znajdują się na tym samym poziomie, co zapewnia zrównoważenie.
• Węzły mają minimalną i maksymalną liczbę kluczy (określaną przez stopień drzewa).
• Zapewnia efektywne wyszukiwanie, wstawianie i usuwanie z logarytmiczną złożonością.

Przykład struktury węzła drzewa B:

struct BTreeNode {
    keys: array of keys,
    children: array of pointers to child nodes,
    leaf: boolean indicating if node is leaf
}

Taka struktura pozwala efektywnie pracować z dużymi ilościami danych, minimalizując liczbę odwołań do dysku.