Definition - B-Baum

• Generalisierungen:
  • Wurzelbaum
• Involvierte Definitionen:
  • siehe auch Binärbaum
• Veranstaltung: IR
• Referenz:
  • @wagenpfeil2024 (p. 24 f.)
  • Topic 07, Part 04 - B-Tree Indexes - Dr. Daniel Soper

⠀

Definition: B-Baum

Als B-Baum (kurz für bspw. Balancierter Baum¹) bezeichnen wir einen balancierten Suchbaum zur effizienten Verwaltung großer Datenmengen.

Jeder Knoten eines B-Baums enthält mehrere Schlüssel und Zeiger auf Teilbäume, die jeweils bestimmte Wertebereiche abdecken. Zu jedem Schlüssel kann außerdem ein Wert gespeichert werden.

Dadurch, dass der Baum ausbalanciert ist, befinden sich alle Blätter auf derselben Ebene. Das hält die Höhe des Baums gering, was wiederum die Zugriffszeiten beim Suchen, Einfügen und Löschen erheblich reduziert - in der Regel müssen neue Ebenen des B-Baums nämlich zunächst in den RAM geladen werden. Je mehr Ebenen, desto mehr teure Lese-Operationen.

Beim Einfügen oder Löschen werden die Knoten automatisch neu organisiert, um das Gleichgewicht des Baums zu erhalten.

Footnotes

1. Die tatsächliche Herkunft des Namens ist leider nicht festgehalten worden. ↩