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

B-Baum

Bin�rb�ume wurden entwickelt, um eine effektive Suchstruktur f�r den Hauptspeicher zu konzipieren. Diese Speicherstrukturen eignen sich nicht unmittelbar f�r den Plattenspeicher, da sie sich nicht direkt auf Seiten abbilden lassen. Man verwendet daher nur die Idee des bin�ren Suchens bei den B-B�umen. Ein Knoten des Baumes entspricht einer Seite oder einem Block des Plattenspeichers. B-B�ume bieten sowohl bei der Auslastung als auch f�r die Anzahl der Suchzugriffe feste obere Grenzen. B-B�ume sind nach Bayer benannt.

In edb ist ein B-Baum-Applet enthalten, das den Aufbau eines B-Baumes (INSERT und DELETE) demonstriert.

B-Baum
B-Baum vom Typ 1 der H�he 2

Ein B-Baum der H�he h vom Typ k ist ein gerichteter Baum mit folgenden Eigenschaften:

  1. Der Baum ist vollst�ndig balanciert. d.h. jeder Weg von der Wurzel zum Blatt hat die gleiche L�nge, die H�he h.
  2. Jeder Knoten au�er der Wurzel des Baumes stellt eine Seite einer festen L�nge dar und enth�lt mindestens k und h�chstens 2k Datens�tze. Die Wurzel hat mindestens einen und h�chstens 2k Eintr�ge.
  3. Jeder Knoten hat einen Schl�ssel und einen Nichtschl�sselanteil und ist nach den Schl�sselwerten aufsteigend sortiert.
  4. Alle inneren Knoten (au�er den Bl�ttern} mit n Eintr�gen haben n+1 Kinder.
  5. Ein linker Pfad zeigt auf eine Seite, in der es nur kleinere Schl�sselwerte gibt, ein rechter Pfad dementsprechend auf eine Seite, in der es nur gr��ere Schl�sselwerte gibt
LesenVon der Wurzel ausgehend wird der Schl�sselwert mit dem Ausgangswert verglichen und auf den entsprechenden Nachfolger verzweigt, je nachdem ob der zu vergleichende Wert gr��er oder kleiner als der Schl�sselwert des Vaters ist. Dabei ist die maximale Anzahl der Zugriffe gleich h, der H�he des Baumes.
SchreibenEs wird wie beim Lesen der Knoten bestimmt, auf dem der Satz abgelegt sein m�sste. 1.Fall: Es ist noch gen�gend Platz vorhanden. 2.Fall: Der Knoten ist mit 2k S�tzen gef�llt. In diesem Fall muss der Knoten gesplittet werden
L�schenWie beim Schreiben wird der Knoten bestimmt, auf dem der Satz gel�scht werden muss. 1. Fall: Es sind noch mehr als k S�tze in diesem Knoten und das L�schen erfolgt ohne Zusammenlegen von Knoten. 2. Fall: Der Knoten enth�lt weniger als k S�tze. In diesem Fall muss der Knoten mit einem anderen zusammengelegt werden, in der umgekehrten Vorgehensweise wie beim Schreiben
SpeichereffizienzAls Verwaltungsdaten benutzen B-B�ume nur die Zeiger auf die nachfolgenden Bl�cke. Anders als bei der ISAM-Speicherstruktur werden die Schl�ssel gemeinsam mit den Nutzdaten gespeichert. Durch den durch die Definition vorgegebenen Fuellgrad? ist eine Ausnutzung von mindestens 50 % erreicht.

Zur Demonstration eines B-Baumes k�nnen Sie den B-Baum-Zeichner in http://edb.gm.fh-koeln.de/ nutzen.

Vorgehensweise beim Schreiben und Splitten

Der Knoten, auf dem der neue Satz liegen m�sste, h�tte (2k + 1) Elemente und wird daher in drei Teile geteilt.

  • Der erste Teil enth�lt die ersten k Elemente, dieser Anteil wird im alten Knoten gespeichert.
  • Der zweite Teil enth�lt die Elemente mit den k gr��ten Schl�sselwerten. F�r diesen Teil wird ein neues Blatt auf der gleichen Stufe angelegt.
  • Der mittlere Teil, also das (k+1 )-te Element, wird im Vater gespeichert.
  • Falls der Vater schon 2k Elemente hat, muss er nach dem gleichen Verfahren gesplittet werden. Im ung�nstigsten Fall setzt sich das Verfahren bis zur Wurzel fort und es muss eine neue Wurzel eingerichtet werden; die H�he des Baumes erh�ht sich um eins.

Vorgehensweise beim L�schen

  • Falls es sich um ein Blatt handelt, also einen Knoten ohne Nachfolger, wird der Eintrag einfach entfernt.
  • Falls es sich um einen inneren Knoten handelt, wird der n�chstgr��ere oder n�chstkleinere Schl�ssel gesucht und an Stelle des zu l�schenden Wertes platziert.
  • Falls ein Knoten weniger als k-Elemente hat, wird der Knoten mit seinem Nachbarn ausgeglichen oder verschmolzen.
  • Der Ausgleich ist eine gleichm��ige Verteilung des Inhalts beider Knoten.
  • Das Verschmelzen ist das Zusammenf�gen beider Knoten. Dies ist nur m�glich, wenn beide Knoten minimal besetzt sind. Ein Schl�ssel aus dem Vaterknoten wird dabei nach unten verpflanzt, so dass im ung�nstigsten Fall dieser Vaterknoten unterbesetzt ist und sich das Verfahren nach oben fortsetzt. Da das L�schverfahren beim B-Baum sehr aufw�ndig ist, wird in der Praxis oft auf das Verschmelzen und Ausgleichen verzichtet und damit eine Unterbesetzung in Kauf genommen.

Siehe auch: B-Plus-Baum, Physische Speicherstruktur

Kategorien: Speicherstrukturen, B