home  |  suche  |  kontakt/johner  |  institut 
studierende  |  tech-docs  |  mindmailer 

B-Bäume

B-Bäume sind nach Rudolph Bayer benannt, dabei steht das B nicht für binär, sondern Knoten in einem B-Baum können mehr als ein Element haben. Jeder B-Baum hat eine Ordnung m, dabei gilt

  • alle Wege von der Wurzel zu den Blättern sind gleich lang
  • alle Knoten besitzen die gleiche Anzahl von (möglichen) Einträgen (2m)
  • jeder Knoten besitzt zwischen m und 2m Elementen (Ausnahme bei der Wurzelt, sie kann 1 bis 2m Elemente besitzen)
  • Blattknoten haben keine Nachfolger
  • jeder sonstige Knoten hat i+1 Nachfolger, falls i die Anzahl der Elemente des Knotens ist.

Ein B-Baum könnte wie folgt aussehen, dabei stehen zwischen den Elementen eines Knotens immer Verweise, die auf den nächsten Unterbaum verweisen. Eine Reihenfolge nach der Größe der Elemente wird dabei beigehalten.

Suchen in B-Bäumen

Soll nach einem Element in einem B-Baum gesucht werden wird folgendermaßen vorgegangen

  • Start beim Wurzelknoten x und überprüfen ob x gleich oder größer einem Element ist,
  • wenn x gleich einem Element, wurde er gefunden und kann zurückgeliefert werden
  • wenn x > einem Element ist, wird im nächsten Unterbaum gesucht, auf den der Verweis zeigt
  • weiteres Vorgehen, wie im Wurzelknoten
  • sobald ein Blattknoten erreicht ist, überprüfen ob x das Element ist, wenn ja dann ist das Element gefunden, wenn nein ist das Element im B-Baum nicht enthalten.

4.2.2 Einfügen in B-Bäume

Beim Einfügen von Elementen in B-Bäume wird wie folgt vorgegangen

  • Suchen nach der passenden Position des Elements und einfügen
  • Überprüfen, ob im Knoten <= 2m Elemente sind
  • wenn ja, Element dort belassen
  • wenn nein, das mittlere Element einen Knoten nach oben verschieben, dort auch wieder auf <= 2m Elemente prüfen und gegebenenfalls rekursiv fortfahren

Ein kleines Beispiel um das Vorgehen des Einfügens zu verdeutlichen. Es sollen die Zahlen 1, 5, 2, 6, 7, 4 in einen B-Baum eingefügt werden.

Löschen in B-Bäumen

Beim Löschen eines Elements müssen folgende Regeln beachtet werden

  • es müssen mindestens m Elemente im Knoten bleiben
  • Element ist ein Blatt --> Element löschen
  • Element ist ein Knoten --> Element löschen und durch nächst kleineres ersetzen

In beiden Fällen müssen eventuell Unterlauf-Behandlungen durchgeführt werden. Dabei gibt es zwei verschieden Möglichekeiten

  1. Reorganisation: Falls die Seite und ihre Nachbarseite nach dem Löschen die Mindestanzahl an Elemente hat, können die Elemente neu verteilt werden: neues mittleres Element bestimmen, dieses wird neues Elternelement, die verbleibenden Elemente auf beide Seiten verteilen.
  2. Zusammenlegen von Seiten: Falls die Seite und ihre Nachbarseite nach dem Löschen nicht mehr über genügend Elemente verfügen, werden die Elemente der beiden Seiten und des eingeschlossenen Elternelements auf eine Seite zusammengelegt.

Das Löschen eines Elements und beide Möglichkeiten der Unterlauf-Behandlungen sollen anhand eines Beispiels verdeutlicht werden.

Das 1. Beispiel zeigt das einfach Löschen eines Elements ohne weitere Unterlaufbehandlung.

Das zweite Beispiel zeigt das Löschen eines Elements mit nachfolgener Reorganisation als Unterlaufbehandlung.

Das letzte Beispiel verdeutlicht das Zusammenlegen von Seiten als Unterlaufbehandlung nach dem Löschen eines Elements.