B⁺-Baum

B⁺-Baum

Der B+-Baum ist eine Erweiterung des B-Baumes. Bei einem B+-Baum werden die eigentlichen Datenelemente nur in den Blattknoten gespeichert, während die inneren Knoten lediglich Schlüssel enthalten.

Ein einfaches Beispiel eines B+-Baumes welches die Datenwerte 1-7 verlinkt. Die roten Knoten erlauben eine schnelle in-order Traversierung.

Ziel dieses Verfahrens ist es, die Zugriffszeiten auf die Datenelemente zu verbessern. Dazu muss man die Baumhöhe verringern, was bedeutet, dass der Verzweigungsgrad des Baumes wachsen muss. Da die maximale Speicherbelegung eines Knotens begrenzt ist, gewinnt man durch das Verlegen der Daten in die Blätter mehr Platz für Schlüssel bzw. Verzweigungen in den inneren Knoten.

Ein weiteres Ziel kann sein, die Operation Bereichssuche zu verbessern, bei der alle Daten in einem gewissen Schlüsselintervall sequentiell durchlaufen werden. Werden die Daten nämlich ausschließlich in den Blättern abgelegt, muss der jeweils nächste Datensatz der Sequenz nicht wieder von der Wurzel aus gesucht werden.

Sei s der Schlüssel des aktuellen Datensatzes der Sequenz. Ist dieser Schlüssel nicht an rechtester Stelle in einem Blatt abgelegt, so befindet sich sein nachfolgender Datensatz (mit dem Schlüssel s') im selben Blatt rechts neben s. Ist der Schlüssel doch an rechtester Stelle eines Blattes gespeichert, müsste die Suche wiederum bei der Wurzel beginnen. Dies kann vermieden werden, indem man die Blätter des B+-Baumes, wie beim B*-Baum, in einer linearen Liste miteinander verbindet. Dieses Feature wird häufig in die Definition des B+-Baumes mit aufgenommen.

Wesentlicher Vorteil eines externen Suchbaums (Daten nur in den Blättern), ist die Möglichkeit des Einsatzes von Sekundärindizes. Sie stellen einen weiteren – nach anderen Kriterien sortierbaren – Suchbaum auf denselben Daten zur Verfügung.

Inhaltsverzeichnis

Struktur

Jeder Knoten besteht aus n Suchschlüsseln und n + 1 Pointern. Davon zeigt in den Blattknoten der letzte Pointer immer auf das nächstliegende Blatt (außer dem letzten Knoten). Die restlichen Pointer in den Blattknoten zeigen jeweils auf die Datenelemente, die durch die Suchschlüssel repräsentiert werden.

Beispiel: n = 3

  • alle Knoten haben maximal 3 Suchschlüsselwerte und maximal 4 Pointer
  • Wurzel hat mindestens einen Wert, also 2 Pointer
  • Innere Knoten haben mindestens 1 Suchschlüssel und 2 Pointer
  • Blätter haben mindestens 2 Suchschlüssel und 3 Pointer


Regeln

  • Wurzel: Mindestens zwei Pointer besetzt
  • Mittelknoten: Mindestfüllgrad \left\lceil \frac{n+1}{2} \right\rceil Pointer
  • Blätter: Mindestfüllgrad \left\lfloor\frac{n+1}{2}\right\rfloor Pointer (zeigen auf Datenblöcke, Pointer auf Nachbarknoten werden nicht gezählt)

Für Mittel- und Wurzelknoten gilt: Der links unter einem Suchschlüssel startende Pointer führt zu einem Knoten, dessen größter Suchschlüsselwert kleiner dem Suchschlüsselwert ist. Der rechts unter einem Suchschlüssel stehende Pointer führt zu einem Knoten, dessen kleinster Suchschlüsselwert größer gleich dem Suchschlüsselwert ist.

Suchen

Beispiel anhand von obiger Grafik:

  • Suche von Wert „9“: Start im Wurzelknoten, Wert ist größer als 5, also gehe rechten Weg den Pointer entlang, durchsuche Blatt, nicht gefunden, Suche erfolglos.
  • Suche von Wert „2“: Start im Wurzelknoten, Wert ist kleiner als 3, also gehe linken Weg dem Pointer entlang und durchsuche Blatt, gefunden, Suche erfolgreich.

Einfügen

Es gibt grundsätzlich 2 Möglichkeiten beim Einfügen von neuen Suchschlüsseln: 1. Es gibt im betreffenden Blatt Platz. 2. Es gibt keinen Platz.

Im ersten Fall kann der Wert einfach in das Blatt eingetragen werden. (siehe Suchen)

Im zweiten Fall wird der Wert an das Blatt "virtuell" angefügt. Jetzt ergibt sich eine Überfüllung des Blattes. Es muss also geteilt werden. Dabei ist zu beachten, dass bei ungerader Suchschlüsselanzahl in einem Blatt das linke Teilblatt einen Suchschlüsselwert mehr als das rechte bekommt (Beispiel: n=4, 1 einfügen, links: 3 Werte & rechts 2 Werte). Dies kann möglicherweise eine Kettenreaktion verursachen, die nach oben im Baum durchpropagiert werden muss, da ja die Mittel- und Wurzelknoten angepasst werden müssen.

Löschen

Der Wert wird im Baum gesucht. Wenn er gefunden wird, dann wird der Wert entfernt. Eventuelle Änderungen müssen durch den Baum propagiert werden. Dabei gibt es zu beachten, dass unterbefüllte Knoten mit anderen verschmolzen werden müssen. Hier gibt es durchaus unterschiedliche Techniken. Am gebräuchlichsten sollte es sein, den Knoten mit seinem linken Nachbarn zu verschmelzen (wenn es keinen linken gibt, dann den rechten) und bei Bedarf diesen bei Überfüllung wieder nach obiger Regel zu teilen.

Vorteile

  • ist immer balanciert
  • für Bereichsanfragen (in Datenbanksystem) optimal geeignet, da immer alle Blätter sortiert und durch Pointer untereinander verbunden, sodass leicht iterierbar

Siehe auch

Weblinks

  • Applet zur Simulation [1]
  • Paper "Implementing Deletion in B+-trees" [2]

Wikimedia Foundation.

Игры ⚽ Нужна курсовая?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Baum (Familienname) — Baum ist ein Familienname. Herkunft und Bedeutung Der Familienname kann vom Baum als der Pflanze herrühren oder ein jüdischer Familienname in Anspielungen auf Abraham als Stammvater sein. Bekannte Namensträger Inhaltsverzeichnis A B C D E F G H I …   Deutsch Wikipedia

  • Baum — is a German surname meaning tree and may refer to:* Antoine Baum (Antoine Baumé), (1728 1804), French chemist * Bernie Baum, American song writer * Eric Baum, American computer scientist and artificial intelligence researcher * Edgar Schofield… …   Wikipedia

  • Baum (Begriffsklärung) — Baum (westgermanisch boum „Baum“, „Baumstamm“) bezeichnet: Baum in der Botanik die Wuchsform einer Pflanze Baum (Familienname), Namensträger siehe dort. Baum (Graphentheorie), in der Graphentheorie einen speziellen Graphen und in der Informatik… …   Deutsch Wikipedia

  • Baum-Wolfsmilch — (Euphorbia dendroides) Systematik Familie: Wolfsmilchgewächse (Euphorbiaceae) …   Deutsch Wikipedia

  • Baum-Hasel — Systematik Eurosiden I Ordnung: Buchenartige (Fagales) Familie …   Deutsch Wikipedia

  • Baum (Steuerelement) — Baum, der ein Verzeichnis mit Unterverzeichnissen darstellt (im Dateimanager Konqueror Ein Baum (engl: Tree view oder treeview) ist ein Steuerelement einer grafischen Benutzeroberfläche, das eine hierarchisch gegliederte Liste darstellt und… …   Deutsch Wikipedia

  • Baum'e — Bau m[ e] , a. Designating or conforming to either of the scales used by the French chemist Antoine Baum[ e] in the graduation of his hydrometers; of or relating to Baum[ e] s scales or hydrometers. There are two Baum[ e] hydrometers. One, which… …   The Collaborative International Dictionary of English

  • Baum-Strelitzie — (Strelitzia nicolai) Systematik Monokotyledonen …   Deutsch Wikipedia

  • BAUM, OSCAR — (1883–1941), Czechoslovak author who wrote in German. Baum was a member of the Prague circle of max brod and franz kafka . Losing his sight as a boy, Baum was trained at the Vienna Institute for the Blind as an organist and pianist and… …   Encyclopedia of Judaism

  • Baum der Sibyllen (Étampes) — Baum der Sibyllen in Étampes Als Baum der Sibyllen wird ein Fenster bezeichnet, das sich in der Kirche Notre Dame du Fort in Étampes, einer Stadt im Département Essonne in der Region Île de France, befindet. Das Bleiglasfenster entstand um… …   Deutsch Wikipedia

  • BAUM, HERBERT — (1912–1942), German Communist and anti Nazi fighter. Baum was a member of the German communist youth movement from 1932 and led a clandestine Jewish communist cell in Berlin from 1936. In 1937 he and his wife Marianne organized a political circle …   Encyclopedia of Judaism

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”