www.wikidata.de-de.nina.az

B Baum Der ist eine Daten bzw Indexstruktur in der Informatik und eine Variante des B Baums die 1973 von Donald Knuth vo

B*-Baum

Der B*-Baum ist eine Daten- bzw. Indexstruktur in der Informatik und eine Variante des B-Baums, die 1973 von Donald 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). 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, eine andere B-Baum-Variante, bei der Daten nur in den Blattknoten gespeichert und durch die Verkettung der Blattknoten Bereichsanfragen effizienter unterstützt werden.

Definition Bearbeiten

Knuth definiert einen B*-Baum der Ordnung durch folgende Forderungen:

  1. Alle Knoten außer die Wurzel haben maximal Kinder,
  2. alle Knoten außer Wurzel und Blätter haben mindestens Kinder,
  3. die Wurzel hat mindestens und maximal Kinder,
  4. alle Blätter haben die gleiche Entfernung von der Wurzel und
  5. alle Knoten, die keine Blätter sind, mit Kindern enthalten Schlüssel.

Unterschiede zum B-Baum Bearbeiten

Überlaufbehandlung in einem B*-Baum der Ordnung 6: Beim ersten Insert läuft der Knoten in den 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. Der Hauptunterschied zu B-Bäumen liegt in der zweiten Forderung, dass Knoten zu 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 Schlüssel, so ist der Schlüssel 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 und 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 gilt in einem B*-Baum der Ordnung mit Schlüsseln: . Im B-Baum hingegen müssen Knoten für einen Zugriff geladen werden.

Anwendung Bearbeiten

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 Bearbeiten

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. 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. Vom National Institute of Standards and Technology werden die Varianten des B-Baums nach Comers Unterteilung geführt.

Einzelnachweise Bearbeiten

  1. ↑ Knuth, D. E.: The Art of Computer Programming, Volume III: Sorting and Searching Addison-Wesley, 1973, Seite 488
  2. ↑ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms. 2. Auflage. MIT Press, Cambridge MA 2001, ISBN 0-262-03293-7.
  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, abgerufen am 24. Januar 2011. Available from: https://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, abgerufen am 24. Januar 2011. Available from: https://xlinux.nist.gov/dads/HTML/bplustree.html
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Der B Baum ist eine Daten bzw Indexstruktur in der Informatik und eine Variante des B Baums die 1973 von Donald Knuth vorgeschlagen wurde und sich vom B Baum in der Forderung unterscheidet dass Knoten mindestens zu 2 3 gefullt sein mussen anstatt nur 1 2 gefullt 1 2 Dies wird vor allem durch eine veranderte Split Strategie erreicht bei der 2 volle Knoten auf 3 Knoten mit einem Fullgrad von 2 3 aufgeteilt werden Der Name wird aus historischen Grunden oftmals fur den B Baum verwendet eine andere B Baum Variante bei der Daten nur in den Blattknoten gespeichert und durch die Verkettung der Blattknoten Bereichsanfragen effizienter unterstutzt werden Inhaltsverzeichnis 1 Definition 2 Unterschiede zum B Baum 3 Anwendung 4 Benennung 5 EinzelnachweiseDefinition BearbeitenKnuth definiert einen B Baum 1 der Ordnung m displaystyle m nbsp durch folgende Forderungen Alle Knoten ausser die Wurzel haben maximal m displaystyle m nbsp Kinder alle Knoten ausser Wurzel und Blatter haben mindestens 2 m 1 3 displaystyle frac 2m 1 3 nbsp Kinder die Wurzel hat mindestens 2 displaystyle 2 nbsp und maximal 2 2 m 2 3 1 displaystyle 2 left lfloor frac 2m 2 3 right rfloor 1 nbsp Kinder alle Blatter haben die gleiche Entfernung von der Wurzel und alle Knoten die keine Blatter sind mit k displaystyle k nbsp Kindern enthalten k 1 displaystyle k 1 nbsp Schlussel Unterschiede zum B Baum Bearbeiten nbsp Uberlaufbehandlung in einem B Baum der Ordnung 6 Beim ersten Insert lauft der Knoten in den Nachbarknoten uber beim zweiten Insert laufen beide Knoten uber 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 Baumen liegt in der zweiten Forderung dass Knoten zu 2 3 displaystyle 2 3 nbsp gefullt sein mussen Dazu ist eine Anpassung des B Baum Algorithmus zur Uberlaufbehandlung notig Anstatt bei einem Uberlauf sofort einen neuen Knoten anzulegen wird zuerst uberpruft ob im rechten Nachbarknoten noch Platz ist Ist dies der Fall werden die Schlussel der beiden Knoten und der trennende Schlussel im Elternknoten gleichmassig auf die beiden Knoten verteilt Enthalt der zweite Knoten j displaystyle j nbsp Schlussel so ist der Schlussel m j 2 1 displaystyle lfloor m j 2 rfloor 1 nbsp der neue trennende Schlussel Ist im Nachbarknoten ebenfalls kein Platz wird ein neuer Knoten angelegt und die Schlussel der beiden ursprunglichen Knoten der eingefugte Knoten sowie der trennende Schlussel des Elternknoten werden auf alle drei Knoten verteilt Dabei sind die Schlussel 2 m 2 3 1 displaystyle lfloor 2m 2 3 rfloor 1 nbsp und 4 m 1 3 displaystyle lfloor 4m 1 3 rfloor nbsp die trennenden Schlussel im Elternknoten Die hohere Datendichte hat einen hoheren Verzweigungsgrad und somit eine geringere Baumhohe zur Folge Dadurch steigert sich die Performance gegenuber dem B Baum da weniger Knoten geladen werden mussen Fur das Level eines Schlussels und damit die fur einen Zugriff notigen Knoten l displaystyle l nbsp gilt in einem B Baum der Ordnung m displaystyle m nbsp mit N displaystyle N nbsp Schlusseln l 1 log 2 m 1 3 N 1 2 displaystyle l leq 1 log lceil 2m 1 3 rceil frac N 1 2 nbsp Im B Baum hingegen mussen l 1 log m 2 N 1 2 displaystyle l leq 1 log lceil m 2 rceil frac N 1 2 nbsp Knoten fur einen Zugriff geladen werden 1 Anwendung BearbeitenDer B Baum ist wie schon der B Baum auf die Ablage im Sekundarspeicher optimiert Zwischen dem Hauptspeicher und dem Sekundarspeicher werden Datenblocke auch Seiten engl Pages genannt fester Grosse ubertragen Da Zugriffe auf den Sekundarspeicher gegenuber Berechnungen und Zugriffen auf den Hauptspeicher sehr lange dauern muss die Zahl der fur eine Operation notigen Seiten aus dem Sekundarspeicher minimiert werden Die Grosse der Knoten wird deshalb so gewahlt dass diese genau in eine Seite passen Dadurch eignen sich die verschiedenen Varianten des B Baums sehr gut fur Datenbanken und Dateisysteme Benennung BearbeitenAls B Baum wird haufig 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 fur die spater als B Baum bezeichnete Variante so dass sich eine eindeutige Abgrenzung nicht mehr vollstandig durchsetzen konnte 5 Vom National Institute of Standards and Technology werden die Varianten des B Baums nach Comers Unterteilung gefuhrt 6 7 Einzelnachweise Bearbeiten a b c d Knuth D E The Art of Computer Programming Volume III Sorting and Searching Addison Wesley 1973 Seite 488 a b Thomas H Cormen Charles E Leiserson Ronald L Rivest Clifford Stein Introduction to Algorithms 2 Auflage MIT Press Cambridge MA 2001 ISBN 0 262 03293 7 Comer D Ubiquitous B Tree ACM Computing Surveys 11 1979 2 121 137 Wedekind H On the Selection of Access Paths in a Data Base System IFIP Working Conference Data Base Management 1974 385 397 Bayer R amp Unterauer K Prefix B Trees ACM Trans Database Syst 1977 2 11 26 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 abgerufen am 24 Januar 2011 Available from https xlinux nist gov dads HTML bstartree html 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 abgerufen am 24 Januar 2011 Available from https xlinux nist gov dads HTML bplustree html Abgerufen von https de wikipedia org w index php title B Baum amp oldid 228923211