Notizen

B-Bäume

tagsdatenstrukturen, algorithmen

Ein B-Baum der Ordnung ist ein -ärer Suchbaum mit folgenden Einschränkungen:

  1. Alle Blätter liegen in der selben Schicht (haben die gleiche Tiefe)
  2. Knoten mit Nachfolgern und Werten haben genau Nachfolger
  3. Alle Knoten außer der Wurzel haben mindestens und maximal Werte (d.h. jeder Knoten mit Ausnahme der Wurzel und der Blätter hat wenigstens Nachfolger
  4. Die Suchbaumeigenschaft, in diesem Fall Intervallbaumeigenschaft ist erfüllt:
    • Seien die Werte eines Knotens, dann gilt
    • Für alle Werte mit linkem und rechtem Teilbaum gilt:
      Werte linker Teilbaum < Wert < Werte rechter Teilbaum

Beispiel

B-Baum der Ordnung 4

Beobachtungen

  • Jeder Knoten (Außer Wurzel und Blätter) hat:
    • Nachfolger: Mindestens
    • Werte:
      • Mindestens
      • Maximal
  • Knoten mit Werten haben Nachfolger (bis auf Blätter)

Motivation

  • Kompletter Datensatz passt nicht in den Hauptspeicher
  • Wahlfreier Zugriff auf externe Speicher ist langsam

Idee

  • Ein Knoten enthält einen großen Block, der vom Medium gelesen wird
  • Möglichst viele Operationen sollen im Hauptspeicher durchgeführt werden, bevor ein neuer Block geladen oder geschrieben wird

Abschätzung der Höhe

Sei ein B-Baum der Ordnung mit Knoten, dann lässt sich die Höhe wie folgt abschätzen:

Operationen

Suchen

Komplexität:

  • Suche im Knoten: BC , WC/AC/Misserfolg einfach, mit binärere Suche
  • Suche im Baum: BC , WC/AC/Misserfolg

Einfügen

  • Einfügestelle ist immer ein Blatt das geht aus den Anforderungen des B-Baums hervor, es gibt nie eine Leerreferenz die kein Blatt ist
  • Folgende Fälle können auftreten:
    1. Fall: B-Baum ist leer
      • Wurzel/Blatt mit Wert anlegen
    2. Fall: B-Baum ist nicht leer
      • Einfügestelle ist in einem Blatt, das noch einen Wert aufnehmen kann: Wert einsortieren
      • Einfügestelle ist in einem vollen Blatt: Blatt teilen, Median (Nicht Durchschnitt) in den Vorgänger einfügen

Wie wächst der Baum, wenn wir keine neuen Knoten unten an die Blätter anhängen dürfen?

Der Baum wächst über den Suchweg nach oben

Beispiel: Einfügen vom Wert in den oberen Baum:

Komplexität:

Entfernen

  • Suchen des zu löschenden Elements
  • Fall 1: Wert wird nicht aus einem Blatt entfernt
    • Linker und rechter Nachfolger sind immer vorhanden (Definition)
    • Wert wird durch den linkesten Wert in seinem rechten Teilbaum ersetzt (Inorder-Nachfolger)
    • Inorder-Nachfolger ist zu löschen (-> 2. Fall)
  • Fall 2: Wert ist aus einem Blatt zu entfernen
    • Fall 1: Das Blatt ist die Wurzel
      • Entferne diesen Wert (Baum ist dann leer)
    • Fall 2: Das Blatt ist nicht die Wurzel
      • Beachtung der Mindestbefüllung
      • Falls: Blatt enthält mehr als Werte: Entfernen
      • Sonst: Entfernen und B-Baum-Eigenschaft wiederherstellen

Komplexität:

Wiederherstellung der B-Baum-Eigenschaft

  • Fall 1: Geschwisterknoten haben noch genug Werte -> Balancieren

  • Fall 2: Geschwisterknoten haben beide nicht mehr genug Werte -> Vereinigung

Backlinks