• Artikel
• Bearbeiten
• Historie
• Druckansicht

B-Baum

Ein Knoten eines B-Baumes speichert

• eine variable Anzahl s von Schlüsseln k_1 .. k_s,
• optional pro Schlüssel ein zugeordnetes Datenelement und
• eine Markierung isLeaf, die angibt, ob es sich bei dem Knoten um ein Blatt oder einen inneren Knoten handelt.
• Falls es sich um einen inneren Knoten handelt, zusätzlich s+1 Verweise auf Kindknoten.

Alle Blattknoten des B-Baumes befinden sich in gleicher Tiefe. Die Tiefe der Blattknoten ist gleich der Höhe h des Baumes.

Es gilt folgende Beschränkung für die erlaubte Anzahl von Kindverweisen bzw. Schlüsseln pro Knoten. Dazu wird eine Konstante t festgelegt, die den minimalen Verzweigungsgrad von Baumknoten angibt.

• Alle Knoten außer der Wurzel haben
  • mindestens t-1 und höchstens 2t-1 Schlüssel und
  • mindestens t und höchstens 2t Kindverweise, wenn es sich um innere Knoten handelt.
• Die Wurzel hat
  • mindestens 1 und höchstens 2t-1 Schlüssel, wenn der Baum nicht leer ist, und
  • mindestens 2 und höchstens 2t Kindverweise, wenn die Höhe des Baumes größer 0 ist.