B+-Baum

B+-Bäume trennen wie ISAM-Strukturen strikt zwischen Nutzdaten und Schlüsseldaten. Im Schlüsselbereich sind sie wie B-Bäume aufgebaut, die eigentlichen Daten liegen getrennt davon in einem eigenen Speicherbereich. Sie vereinigen daher die Vorteile von B-Bäumen mit denen der ISAM-Speicherstruktur.

B+-Baum
B+ -Baum

Knotenstruktur des B+-Baumes

  1. Die Blattknoten enthalten ausschließlich Nutzdaten und sind in einer linearen Liste geordnet.
  2. Die inneren Knoten enthalten nur die Schlüsselwerte mit Verweisen auf die Blattknoten. Sie sind wie B-Bäume aufgebaut.
  3. Ein linker Zeiger eines inneren Knoten verweist auf ein Blatt, in dem nur Nutzdaten mit kleineren Schlüsselwerten enthalten sind.
  4. Ein rechter Zeiger verweist auf ein Blatt mit größeren Schlüsselwerten.
LesenDer Suchprozess startet in der Wurzel und sucht im B-Baum-Bereich nach dem Zeiger, der auf den entsprechenden Satz verweist. Die maximale Anzahl der Zugriffe ist die Höhe des Baumes h
SchreibenWie beim Lesen wird der Zielblock ermittelt. Im Falle des Überlaufs wird der Block gesplittet und der Indexknoten um einen Repräsentanten ergänzt. Die Anzahl der Zugriffe ist minimal 1 und maximal 2h+1.
LöschenWie bei den B-Bäumen können Blätter mit zu wenigen Sätzen entstehen (Unterlauf), die das Zusammenlegen von Knoten erforderlich macht. Die Anzahl der Zugriffe ist minimal 1 und maximal h + 1 bei Unterlauf, wenn sich die Umverteilung bis zur Wurzel fortpflanzt.
SpeichereffizienzDie Schlüsselwerte werden doppelt gespeichert, daher gibt es einen etwas höheren Platzbedarf. Der Fuellgrad? der Blätter ist zu 50 % durch die Strukturvorschriften gewährleistet.

Siehe auch: B-Baum

Kategorien: Speicherstrukturen, B