B baum gleiche werte

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.

Inhaltsverzeichnis Show

Vorgehensweise beim Schreiben und Splitten
Vorgehensweise beim Löschen
Warum ist ein B Baum immer balanciert?
Wann ist ein Baum balanciert?
Was ist ein Baum Informatik?

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

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:

Der Baum ist vollständig balanciert. d.h. jeder Weg von der Wurzel zum Blatt hat die gleiche Länge, die Höhe h.
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.
Jeder Knoten hat einen Schlüssel und einen Nichtschlüsselanteil und ist nach den Schlüsselwerten aufsteigend sortiert.
Alle inneren Knoten (außer den Blättern} mit n Einträgen haben n+1 Kinder.
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

Lesen	Von 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.
Schreiben	Es 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öschen	Wie 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
Speichereffizienz	Als 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

Warum ist ein B Baum immer balanciert?

B-Bäume gehören zu den balancierten Bäumen, die Daten sortiert speichern. Im Gegensatz zu den meisten anderen Bäumen werden Elemente hier zunächst in den Blättern eingefügt. B-Bäume wachsen damit nach oben von den Blättern zur Wurzel.

Wann ist ein Baum balanciert?

Definition: Ein binärer Suchbaum heißt AVL-Baum oder höhenbalanciert, wenn sich für jeden Knoten die Höhe seines rechten Teilbaums und die Höhe seines linken Teilbaums um maximal eins unterscheiden.