7.5 Interne Ebene: B- und B*-Bäume

• exakte Definition usw. s. Vorlesung Informatik A
• B-Baum: dynamischer Indexbaum, Knoten im Baum = Seiten die mehrere Indexeinträge enthalten, jeder Indexeintrag zeigt auf Seite in Hauptdatei
• Idee: vollständiges Ausgleichen (Wege zu allen Blättern gleichlang, pro Knoten gleichviele Daten) zu teuer -> (R. Beyer, 1970): jede Seite auß er der Wurzelseite enthält zwischen x und 2x Daten; falls dann n Daten in Hauptdatei reichen log_x(n) Seitenzugriffe
• 'Definition' von B-Bäumen der Ordnung x:
  • jede Seite enthält höchstens 2x Elemente
  • jede Seite auß er der Wurzelseite enthält mindestens x Elemente
  • jede Seite
    • ist entweder Blattseite ohne Nachfolger
    • oder hat y+1 Nachfolger, falls y die Anzahl ihrer Elemente ist
  • alle Blattseiten liegen auf der gleichen Stufe

B- und B*-Bäume Unterschied B-Baum zu B*-Baum

• B-Baum: bei jedem Elementeintrag in Knoten Zeiger auf Seite in Hauptdatei
• B*-Baum: nur von Blattknoten gehen Zeigen auf Seiten in Hauptdatei

Beispiel:

B- und B*-Bäume Operationen (hier am B-Baum)

• Lookup: Suche nach Primärschlüsselwert w in B-Baum
  Start bei Wurzelseite, suche zwischen w₁ und w_y Wert w,
  wenn gefunden: fertig,
  falls nicht gefunden: wenn w_i < w < w_i+1 setze Suche auf Seite p_i fort, wenn w_y < w setze Suche auf Seite p_y fort, wenn w < w₁ setzte Suche auf Seite p₀ fort
  solange bis w gefunden oder Nullzeiger erreicht
• Einfügen: füge Primärschlüsselwert w ein
  Lookup ausführen, passende Seite ermitteln
  falls passende Seite y < 2x Elemente hat: w einsortieren, fertig
  falls passende Seite 2x Elemente hat: neue Seite erzeugen, x Elemente auf alter Seite belassen, x Elemente auf neue Seite, 1 (mittleres Element) nach oben einfügen, evtl. Ausgleich rekursiv bis zur Wurzel fortsetzen
• Löschen: Löschen von Primärschlüsselwert w
  Lookup ausführen,
  w auf Blattseite gefunden: löschen, evtl. Unterlauf behandeln, wenn Blattseite < x Elemente hat
  w nicht auf Blattseite gefunden: löschen, durch lexikographisch nächstgröß eres (oder nächstkleinere) Element ersetzen, evtl. Unterlauf behandeln

Quicky: Nacheinander 20, 40, 10, 30, 15, 35, 7, 26, 18, 22, 5, 42, 13, 46, 27, 8, 32, 38, 24, 45, 25 in B-Baum der Ordnung 2 einfügen;
danach nacheinander 25, 45, 24, 38, 32, 8, 27, 46, 13, 42, 5, 22, 18, 26, 7, 35, 15 wieder löschen