Wat betekent de naam B-boom en hoe is deze opgebouwd?

De B-boom is een gebalanceerde zoekboom, geoptimaliseerd voor het werken met grote hoeveelheden gegevens die op externe opslagmedia worden opgeslagen (bijvoorbeeld op de schijf). De naam "B-boom" komt van het Engelse "Balanced" (gebalanceerd) of "Bayer" — de achternaam van een van de uitvinders.

Belangrijkste kenmerken van de B-boom:

• Elke knoop bevat meerdere sleutels en pointers naar kindknopen, wat de hoogte van de boom vermindert.
• Alle bladeren bevinden zich op hetzelfde niveau, wat de balans garandeert.
• Knopen hebben een minimaal en maximaal aantal sleutels (bepaald door de graad van de boom).
• Biedt efficiënte zoek-, invoeg- en verwijderingsmogelijkheden met logaritmische complexiteit.

Voorbeeld van de structuur van een B-boomknoop:

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

Deze structuur maakt het mogelijk om efficiënt te werken met grote hoeveelheden gegevens, terwijl het aantal toegangspogingen tot de schijf wordt geminimaliseerd.