Was bedeutet der Name B-Baum und wie ist er aufgebaut?

Der B-Baum ist ein balancierter Suchbaum, der für die Arbeit mit großen Datenmengen optimiert ist, die auf externen Speichermedien (z.B. auf der Festplatte) gespeichert sind. Der Name "B-Baum" stammt vom englischen "Balanced" (ausgeglichen) oder "Bayer" – dem Nachnamen eines der Erfinder.

Hauptmerkmale des B-Baums:

• Jeder Knoten enthält mehrere Schlüssel und Zeiger auf Kindknoten, was die Höhe des Baums verringert.
• Alle Blätter befinden sich auf derselben Ebene, was die Balance gewährleistet.
• Knoten haben eine minimale und maximale Anzahl von Schlüsseln (bestimmt durch den Grad des Baums).
• Bietet effiziente Suche, Einfügen und Löschen mit logarithmischer Komplexität.

Beispiel für die Struktur eines B-Baum-Knotens:

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

Diese Struktur ermöglicht eine effiziente Arbeit mit großen Datenmengen, indem sie die Anzahl der Zugriffe auf die Festplatte minimiert.