B-Baum

  • Einsatz in DB- oder Dateisystemen
  • Stets vollständig balancierter Baum
  • Sortierung der Daten nach Schlüssel
  • Im Unterschied zu Binärbäumen kann ein Knoten mehr als 2 Kind-Knoten haben
  • Einfügen, Suchen, Löschen in amortisiert logarithmischer Zeit möglich
  • B-Bäume wachsen/schrumpfen von den Blättern hin zur Wurzel

Parameter

t: Ordnung/Verzweigunsgrad des B-Baumes, die minimal erlaubte Anzahl von Kindknoten Die Maximal erlaubte Anzahl an Schlüssel ist 2t-1.

Links