Какво означава името B-дърво и как е устроено?

B-дервото е балансирано дърво за търсене, оптимизирано за работа с големи обеми данни, съхранявани на външни носители (например на диск). Името "B-дерво" произхожда от английските думи "Balanced" (балансирано) или "Bayer" — фамилията на един от изобретателите.

Основни характеристики на B-дервото:

• Всяка възлова точка съдържа няколко ключа и указатели към дъщерни възли, което намалява височината на дървото.
• Всички листа са на едно ниво, което осигурява баланс.
• Възлите имат минимално и максимално количество ключове (определя се от степента на дървото).
• Осигурява ефективно търсене, вмъкване и изтриване с логаритмическа сложност.

Пример за структура на възел от B-дерво:

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

Тази структура позволява ефективна работа с големи обеми данни, минимизирайки броя на достъпите до диска.