B*-Baum

B*-Baum

Der B*-Baum ist eine Daten- bzw. Indexstruktur in der Informatik und eine Variante des B-Baums, die 1973 von Donald Ervin Knuth vorgeschlagen wurde und sich vom B-Baum in der Forderung unterscheidet, dass Knoten mindestens zu 2/3 gefüllt sein müssen (anstatt nur 1/2 gefüllt).[1][2] Dies wird vor allem durch eine veränderte Split-Strategie erreicht, bei der 2 volle Knoten auf 3 Knoten mit einem Füllgrad von 2/3 aufgeteilt werden.

Der Name wird aus historischen Gründen oftmals für den B+-Baum verwendet, einer anderen B-Baum Variante, bei der Daten nur in den Blattknoten gespeichert werden, und durch die Verkettung der Blattknoten Bereichsanfragen effizienter unterstützt werden.

Inhaltsverzeichnis

Definition

Knuth definiert einen B*-Baum[1] der Ordnung m durch

  1. alle Knoten außer die Wurzel haben maximal m Kinder,
  2. alle Knoten außer Wurzel und Blätter haben mindestens (2m − 1) / 3 Kinder,
  3. die Wurzel hat mindestens 2 und maximal 2 \lfloor (2m-2)/3 \rfloor +1 Kinder,
  4. alle Blätter haben die gleiche Entfernung von der Wurzel und
  5. alle Knoten, die keine Blätter sind, mit k Kindern enthalten k − 1 Schlüssel.

Unterschiede zum B-Baum

Überlaufbehandlung in einem B*-Baum der Ordnung 6: Beim ersten Insert läuft der Knoten in der Nachbarknoten über, beim zweiten Insert laufen beide Knoten über und ein neuer Knoten wird angelegt.

Genauso wie im B-Baum enthalten auch im B*-Baum die inneren Knoten Daten.[1] Der Hauptunterschied zu B-Bäumen liegt in der zweiten Forderung, dass Knoten zu 2 / 3 gefüllt sein müssen. Dazu ist eine Anpassung des B-Baum-Algorithmus zur Überlaufbehandlung nötig. Anstatt bei einem Überlauf sofort einen neuen Knoten anzulegen, wird zuerst überprüft, ob im rechten Nachbarknoten noch Platz ist. Ist dies der Fall, werden die Schlüssel der beiden Knoten und der trennende Schlüssel im Elternknoten gleichmäßig auf die beiden Knoten verteilt. Enthält der zweite Knoten j Schlüssel, so ist der Schlüssel \lfloor (m+j)/2 \rfloor + 1 der neue trennende Schlüssel. Ist im Nachbarknoten ebenfalls kein Platz, wird ein neuer Knoten angelegt und die Schlüssel der beiden ursprünglichen Knoten, der eingefügte Knoten, sowie der trennende Schlüssel des Elternknoten werden auf alle drei Knoten verteilt. Dabei sind die Schlüssel \lfloor (2m-2)/3 \rfloor +1 und \lfloor (4m-1)/3 \rfloor die trennenden Schlüssel im Elternknoten.

Die höhere Datendichte hat einen höheren Verzweigungsgrad und somit eine geringere Baumhöhe zur Folge. Dadurch steigert sich die Performance gegenüber dem B-Baum, da weniger Knoten geladen werden müssen. Für das Level eines Schlüssels und damit die für einen Zugriff nötigen Knoten l gilt in einem B*-Baum der Ordnung m mit N Schlüsseln: l \le 1 + \log_{\lceil (2m-1)/3 \rceil} \frac{N+1}{2}. Im B-Baum hingegen müssen l \le 1 + \log_{\lceil m/2 \rceil} \frac{N+1}{2} Knoten für einen Zugriff geladen werden.[1]

Anwendung

Der B*-Baum ist, wie schon der B-Baum, auf die Ablage im Sekundärspeicher optimiert. Zwischen dem Hauptspeicher und dem Sekundärspeicher werden Datenblöcke, auch Seiten (engl. Pages) genannt, fester Größe übertragen. Da Zugriffe auf den Sekundärspeicher gegenüber Berechnungen und Zugriffen auf den Hauptspeicher sehr lange dauern, muss die Zahl der für eine Operation nötigen Seiten aus dem Sekundärspeicher minimiert werden. Die Größe der Knoten wird deshalb so gewählt, dass diese genau in eine Seite passen. Dadurch eignen sich die verschiedenen Varianten des B-Baums sehr gut für Datenbanken und Dateisysteme.

Benennung

Als B*-Baum wird häufig auch eine weitere Variante des B-Baums bezeichnet, die ebenfalls von Knuth beschrieben, aber nicht explizit benannt wird. Diese bekommt von Hartmut Wedekind 1974 ebenfalls den Namen B*-Baum, wird aber 1979 von Douglas Comer zur besseren Abgrenzung als B+-Baum bezeichnet.[3][4][2] Allerdings verwendete Rudolf Bayer schon 1977 den Begriff B*-Baum für die später als B+-Baum bezeichnete Variante, so dass sich eine eindeutige Abgrenzung nicht mehr vollständig durchsetzen konnte.[5] Vom National Institute of Standards and Technology werden die Varianten des B-Baums nach Comers Unterteilung geführt.[6][7]

Einzelnachweise

  1. a b c d Knuth, D. E. The Art of Computer Programming, Volume III: Sorting and Searching Addison-Wesley, 1973, Seite 476-479
  2. a b Cormen, T. H.; Leiserson, C. E.; Rivest, R. L. & Stein, C. Introduction to Algorithms, Second Edition The MIT Press and McGraw-Hill Book Company, 2001
  3. Comer, D. Ubiquitous B-Tree ACM Computing Surveys 11, 1979, 2, 121 - 137
  4. Wedekind, H. On the Selection of Access Paths in a Data Base System IFIP Working Conference Data Base Management, 1974, 385-397
  5. Bayer, R. & Unterauer, K. Prefix B-Trees ACM Trans. Database Syst., 1977, 2, 11-26
  6. Paul E. Black, "B*-tree", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 6. November 2007. (accessed 24. Januar 2011) Available from: http://xlinux.nist.gov/dads/HTML/bstartree.html
  7. Paul E. Black, "B+-tree", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 6. November 2007. (accessed 24. Januar 2011) Available from: http://xlinux.nist.gov/dads/HTML/bplustree.html

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”