Datenbanken Online Lexikon TH Köln, Campus Gummersbach
Aktuelle Änderungen - Suchen:

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