B-Bäume

Einleitung

Früher wurden Datenbanken mittels Listen aufgebaut. Danach kamen die verketteten Listen und um die Zugriffszeit zu minimieren verwendete man Indexdateien. In einer Indexdatei steht ein Schlüsselfeld und ein Zeiger auf einen Datensatz. Somit musste man nicht mehr die ganze Datenbank durchsuchen sondern nur die Indexdatei und wußte genau wo der gesuchte Datensatz ist. Da aber immer mehr Daten verwaltet werden mussten, entstand das Konzept des Baumes. Ein Baum beginnt mit der Wurzel, von der sich die weiteren Knoten nach unten verzweigen, bis sie als Knoten ohne Verzweigungen enden; hierbei spricht man von Endknoten. Jeder Knoten zeigt auf einen Datensatz. Ein Beispiel wäre der Binärbaum, der maximal zwei Verzweigungen hat: nach links, die kleiner Verzweigung, und nach rechts, die größer Verzweigung. Soll ein neuer Eintrag in die Baumstruktur eingefügt werden, muss zuerst die Position in der Struktur bestimmt werden, dies geschieht mittels einer einfachen Vergleichsoperation: Jeder Knoteneintrag wird untersucht, ob der gesuchte Eintrag bereits gefunden wurde. Ist dies nicht der Fall, wird festgestellt, ob der Eintrag kleiner als der Knoteneintrag ist. In diesem Fall wird nach links verzweigt, andernfalls nach rechts. Dies wird solange wiederholt bis der gesucht Eintrag gefunden wurde oder das Baumende erreicht wurde. Der Vorteil des Binärbaumes liegt darin, das er schneller Einträge in einer Datenbank findet, und dieser Vorteil wächst mit der Größe der Datenbank. Aber es kann dazu kommen das ein Baum nicht ausgeglichen ist und somit einer Liste ähnelt. Daher gibt es einen Algorithmus einen Baum wieder in das Gleichgewicht zu bringen. Diese Bäume nennt man AVL-Bäume, sie wurden nach ihren Erfindern G. M. Adelson-Velskii und E. M. Landis benannt. Aber man muss nach jedem Einfügen oder Löschen eines Knotens den Baum neu ausbalancieren.

Der B-Baum

Durch die Größe der Datenbanken konnte man die nun auch größere Indexdatei nicht im Speicher behalten und musste so einzelne Knoten auf einer Seite zusammenfassen. Die Indexdatei wird somit zu einer Ansammlung von Seiten. Die erste Seite wird Quellseite genannt. Innere Seiten werden Knotenseiten genannt und die letzten Seiten bezeichnet man als Endseiten. Diese Struktur wurde von R. Bayer B-Baum genannt.

Jede Seite enthält mehrere Schlüssel, von denen jeder auf einen Datensatz der Datendatei zeigt. Jede Knotenseite enthält überdies Zeiger auf weitere Seiten, die niedrigere und höhere Schlüssel besitzen. Endseiten enthalten keine Zeiger auf weitere Seiten.

Schlüssel Seite

Bild: Der B-Baum.

Regeln

Um die Effizienz von B-Bäumen zu erhöhen, wurden einfache Regeln aufgestellt.

1. Die erste Regel lautet, dass eine Seite mindestens die Hälfte der maximal möglichen Elemente enthalten muss. Ist die höchste Anzahl der Elemente 2n, beläuft sich die Mindestanzahl auf n Elemente. Die Mindestanzahl n wird auch Ordnung des Baumes genannt. Die Quellseite darf allerdings zwischen 1 und 2n Elementen enthalten.

2. Die zweite Regel verlangt, dass sich alle Endseiten auf der gleichen Ebene befinden, um eine ausgeglichene Baumstruktur zu erhalten und einen effizienten Suchweg zu ermöglichen. Daher wächst der Baum von unten nach oben.

Hinzufügen eines Schlüssels

Fügt man ein Element auf der Endseitenebene hinzu, vergrößert sich die Höhe des Baumes aber auf der Quellseitenebene. Daher ist der Baum auch symmetrisch. Will man auf einer Seite die bereits die Höchstzahl an Schlüssel enthält, einen Schlüssel hinzufügen, so wird die Seite in zwei neue Seiten aufgeteilt. Jede neue Seite enthält n Schlüssel, wobei der mittlere Schlüssel in die Vorgängerseite kommt. Der eingefügte Schlüssel wird in der Vorgängerseite korrekt positioniert und zeigt auf die durch die Teilung entstandene linke Seite. Der Ursprüngliche Zeiger zeigt auf die rechte Seite. Enthält die Vorgängerseite nun ihrerseits zu viele Schlüssel, wird sie auf die gleiche Weise geteilt. Dieser Prozeß kann sich bis zur Quellseite fortsetzen. Hier kann nun die Quellseite ihrerseits aufgeteilt werden, die neue Quellseite enthält nur einen einzigen Schlüssel.

hinzufügen

Bild : Hinzufügen eines Schlüssels.

Löschen eines Schlüssels:

Das Löschen von Schlüsseln aus dem B-Baum folgt den gleichen Regeln. Wird ein Schlüssel aus einem Endknoten entfernt, und die Endseite enthält noch mindestens n Schlüssel, ist das Löschen beendet. Reichen jedoch die Einträge in der Seite nicht mehr aus, muss ein Ausgleich erfolgen. Die vom Vorgänger nach rechts führende Seite (oder die nach links führende Seite, wenn der größer Zeiger der Vorgängerseite auf die zu löschende Seite zeigt) wird benutzt um den Baum auszugleichen. Enthält die angrenzende Seite zusammen mit der zu löschenden Seite wenigstens 2n Schlüssel, können die Seiten ausgeglichen werden. Der Ausgleich erfolgt, indem der alte Schlüssel in die zu löschende Seite und ein Schlüssel aus der angrenzenden Seite in die Vorgägnerseite eingefügt werden.

löschen

Bild: Löschen eines Schlüssels aus einer Endseite, bei der ein Ausgleich erforderlich ist.

Enthalten die angrenzende und die zu löschende Seite zusammen weniger als 2n Schlüssel, wird ein Schlüssel in die Seite eingefügt, in der zu wenig Einträge vorhanden sind. Daraufhin werden die beiden angrenzenden Seiten zusammengelegt, d. h. man muss ein Seite löschen.

löschen

Bild : Löschen eines Schlüssel aus einer Endseite, bei der ein Zusammenschluß und die

Löschung einer Seite erforderlich ist.

Wie beim Hinzufügen eines Schlüssels kann sich diese Operation durch den ganzen Baum ziehen. Durch die Löschung des Wurzelknotens schrumpft der Baum um eine Ebene. Soll ein Schlüssel aus einer Knotenseite entfernt werden, ist es erforderlich, den Nachfolger des zu löschenden Schlüssels zu finden. Die geschieht so: Der größte Nachfolger auf der kleineren Seite (der größte der Kleinsten). Ist dies keine Endseite, folgt man dem größer Zeiger bis man eine Endseite erreicht. In der Endseite ist der am weitesten rechts stehende Schlüssel der Nachfolger in der Ordnung. Er ersetzt den gelöschten Knotenschlüssel. Der Endknoten wird in der Größe um eins herabgesetzt. Der Vorgang wird nun so fortgesetzt, als sei der Schlüssel aus einem Endknoten gelöscht worden.

löschen

Bild : Löschung eines Knotens.

Bei der Suche nach einzelnen Einträgen ist der B-Baum am besten. Er stellt jedoch ein Problem dar, wenn eine sortierte oder teilweise sortierte Liste benötigt wird. Um die Elemente oder Schlüssel des Baumes in sortierter Form zu erhalten, muss der Baum sehr oft durchsucht werden. z.B.: Soll der Beispielbaum alphabetisch sortiert werden, benötigt man wieder viel Zeit.

Der B*-Baum:

Eine Lösung ist es den B-Baum etwas zu verändern. So entstand der B*-Baum. Dort wird jeder Schlüssel in absteigenden Knoten solange dupliziert, bis er in einer Endseite enthalten ist. Dort wird er an die letzte Stelle gerückt. Nur Endknoten enthalten Zeiger auf die Datendatei. Die Endknoten werden mit Zeigern in beiden Richtungen verknüpft.

Bild: B*-Baum.

Der B*-Baum wächst wie der B-Baum. Weil der B*-Baum komplexer als der B-Baum ist, ist auch das Löschen und Hinzufügen von Schlüsseln schwieriger. Da manche Schlüssel mehrfach vorkommen, muss man sie auch mehrfach hinzufügen und löschen. Daher muss sich der B*-Baum nach dem Einfügen oder Löschen eines Schlüssels, und dessen Kopie, manchmal neu aufbauen. Der B*-Baum benötigt durch seine Mehrfachkopien auch mehr Speicher. Zwar löst der B*-Baum das Problem mit den sortierten Listen, doch da nur die Endknoten Zeiger auf die Datendatei enthalten, muss immer die gesamte Tiefe des Baumes durchlaufen werden, um einen Zeiger auf die Datendatei zu finden.

Nutzen:

und B*- Bäume werden in Datenbanken eingesetzt, um Datensätze schneller zu

finden. Um die Suchgeschwindigkeiten zu vergleichen ein kleines Beispiel:

Man hat ein Datenbank mit 262.143 Einträgen, so braucht man mit

einer Liste 34.400.000.000 Lesevorgänge

einem AVL-Baum 4.192.513 Lesevorgänge

einem B-Baum 1.530.066 Lesevorgänge

einem B*-Baum 1.572.858 Lesevorgänge

um jeden Eintrag einmal zu finden.

Da man durchschnittlich weniger Lesevorgänge braucht um einen Eintrag in einer Datenbank zu finden werden hauptsächlich B-und B*-Bäume für Datenbanken verwendet.

1223 Worte in "deutsch"  als "hilfreich"  bewertet