W i l l k o m m e n   b e i   [ www.mauspfeil.com ]
 
 



 

Wörterbuch der Bedeutung
<<Zurück
Bitte wählen Sie einen Buchstaben:
A, Ä | B | C | D | E | F | G | H | I | J | K | L | M | N | O, Ö | P | Q | R | S | T | U, Ü | V | W | X | Y | Z | 0-9

Suchen:

(Groß-/Kleinschreibung wird nicht unterschieden)

Google


B-Baum

*** Shopping-Tipp: B-Baum

Ein '''B-Baum''' ist in der Informatik eine Datenstruktur Daten- oder Indexstruktur, die häufig in Datenbanken und Dateisystemen eingesetzt wird. Ein B-Baum ist ein immer vollständig Balancierter Baum balancierter Baum, der Daten sortiert nach Schlüsseln speichert. Das Einfügen, Suchen und Löschen von Daten in B-Bäumen ist in Amortisierte Laufzeitanalyse amortisiert logarithmischer Zeit möglich. B-Bäume wachsen – und schrumpfen – anders als die meisten Suchbäume von den Blättern hin zur Wurzel.

Geschichte und Namensgebung
Der B-Baum wurde 1972 von Rudolf Bayer und Edward M. McCreight entwickelt. Er erwies sich als ideale Datenstruktur zur Verwaltung von Indizes für das relationale Datenmodell, das im gleichen Jahr von Edgar F. Codd entwickelt wurde. Diese Kombination führte zur Entwicklung des ersten SQL-Datenbanksystems System R bei IBM. Die Erfinder lieferten keine Erklärung über die Herkunft des Namens ''B-Baum''. Die häufigste Interpretation ist, dass ''B'' für ''Balancierter Baum balanciert'' steht. Weitere Interpretationen sind ''B'' für ''Bayer'', ''Broad'', ''Bushy'', oder ''Boeing'', da Rudolf Bayer für ''Boeing Scientific Research Labs'' gearbeitet hat. ''B-Baum'' steht '''nicht''' für Binärbaum. Ein Knoten in einem Binärbaum besitzt höchstens zwei Verweise auf Kindknoten, während in einem B-Baum ein Knoten eine Vielzahl von Verweisen auf Kindknoten speichern kann.

Idee und Übersicht
Datenbanksysteme müssen mit sehr großen Datenmengen umgehen, von denen nur ein Bruchteil gleichzeitig in den Hauptspeicher eines Rechners passt. Die Daten sind daher Persistenz (Informatik) persistent auf Hintergrundspeicher (z. B. Festplatten) abgelegt. Für die effiziente Verwaltung werden Datenstrukturen benötigt, welche die charakteristischen Zugriffseigenschaften des Hintergrundspeichers berücksichtigen: Die größte Verzögerung beim Festplattenzugriff entsteht durch die mechanische Positionierung des Schreib-/Lesekopfes. Ist der Schreib-/Lesekopf aber einmal positioniert, kann eine große Datenmenge (ein logischer Sektor) schnell und ohne Belastung des Prozessors über Direct Memory Access DMA eingelesen werden. Binärer Suchbaum Binäre Suchbäume eignen sich für die Strukturierung persistenter Daten nicht, weil sie für ihre Operationen Suchen, Einfügen und Löschen eine Vielzahl wahlfreier Zugriffe benötigen, da jeder Sprung von Knoten zu Knoten eine Neupositionierung des Schreib-/Lesekopfes verursachen würde. B-Bäume minimieren die Anzahl der wahlfreien Zugriffe unter Ausnutzung der charakteristischen Eigenschaften des Hintergrundspeichers. Sie speichern pro Baumknoten eine variable Anzahl von Schlüsseln (statt nur eines einzelnen Schlüssels beim Binärbaum). Mit der Schlüsselanzahl steigt auch die Anzahl der Verweise auf Kindknoten pro Knoten (der Verzweigungsgrad) auf eine variable Anzahl mit festgelegtem Schwankungsbereich von minimal t und maximal 2t (gegenüber zwei beim Binärbaum). Der Parameter t ist wählbar und wird verwendet, um die Datenstruktur so an die Blockgröße des Speichermediums anzupassen, dass ein Baumknoten maximal gerade einen kompletten Block des Speichermediums belegt. Der große Verzweigungsgrad reduziert die Baumhöhe und damit die Anzahl der kostspieligen wahlfreien Zugriffe. Die variable Schlüsselmenge pro Knoten vermeidet häufiges Balancieren des Baumes. Für praktische Anwendungsfälle reduzieren B-Bäume wahlfreie Zugriffe pro Operation sogar auf eine kleine konstante Anzahl. Da ein vollständiger Baum mit Verzweigungsgrad t und Höhe h gerade t^{(h + 1)} - 1 Schlüssel speichert, können bei einem entsprechend groß gewählten t (z. B. t = 1024) bei einer Höhe von h = 4 bereits 1024^{4} - 1 = (2^{10})^{4} - 1 = 2^{40} - 1 Schlüssel gespeichert werden. Da diese Anzahl für alle praktischen Fälle ausreichend groß ist und eine Suchoperation höchstens h+1 Knotenzugriffe benötigt, müssen für jede Suchanfrage höchstens fünf Baumknoten inspiziert werden. Hält man die beiden ersten Baumebenen dauerhaft im Hauptspeicher, so benötigt eine Suche nur noch höchstens drei Festplattenzugriffe. Aus theoretischer Sicht ändert sich dadurch aber nichts an der Komplexität der Suchoperation von O(log(n)) Zugriffen, der konstante Faktor ist aber so klein, dass für praktische Fälle immer eine kleine konstante Zugriffsanzahl ausreicht.

Definitionen
Bild:B-tree-definition.png thumb|320px|right|Abbildung 1: B-Baum #Ein Knoten eines B-Baumes speichert #* eine variable Anzahl s von Schlüsseln k_1 .. k_s, #* optional pro Schlüssel ein zugeordnetes Datenelement und #* eine Markierung ''isLeaf'', die angibt, ob es sich bei dem Knoten um ein Blatt oder einen inneren Knoten handelt. #* Falls es sich um einen inneren Knoten handelt, zusätzlich s+1 Verweise auf Kindknoten. #Für die Schlüssel in einem B-Baum gilt eine gegenüber binären Suchbäumen verallgemeinerte Sortierungsbedingung: #* Alle Schlüssel eines Knotens sind aufsteigend sortiert. #* Bei einem inneren Knoten x teilen seine Schlüssel x.k_i die Schlüsselbereiche seiner Unterbäume x.c_j in s+1 Teilbereiche ein. In einem Unterbaum x.c_j kommen folglich nur Schlüssel k vor, für die gilt: #** k \leq x.k_j, falls j = 1 #** x.k_{j-1} \leq k \leq x.k_j, falls j \in 2..s #** x.k_{j-1} \leq k, falls j = s+1 # Alle Blattknoten des B-Baumes befinden sich in gleicher Tiefe. Die Tiefe der Blattknoten ist gleich der Höhe h des Baumes. # Es gilt folgende Beschränkung für die erlaubte Anzahl von Kindverweisen bzw. Schlüsseln pro Knoten. Dazu wird eine Konstante t festgelegt, die den minimalen Verzweigungsgrad von Baumknoten angibt. #* Alle Knoten außer der Wurzel haben #** mindestens t-1 und höchstens 2t-1 Schlüssel und #** mindestens t und höchstens 2t Kindverweise, wenn es sich um innere Knoten handelt. #* Die Wurzel hat #** mindestens 1 und höchstens 2t-1 Schlüssel, wenn der b Baum nicht leer ist, und #** mindestens 2 und höchstens 2t Kindverweise, wenn die Höhe des Baumes größer 0 ist.

Eigenschaften
Für die Höhe h eines B-Baumes mit n gespeicherten Datenelementen gilt: : h \leq \log_t \left({n+1 \over 2} \right) Damit sind im schlimmsten Fall immer noch Zugriffe auf O(\log(n)) Baumknoten zum Auffinden eines Datenelements notwendig. Die Konstante dieser Abschätzung ist aber deutlich geringer als bei (balancierten) Binärer Suchbaum binären Suchbäumen mit Höhe \log_2(n): : {\log_2(n) \over {\log_t({n+1 \over 2})}} \approx \log_2(t) Bei einem minimalen Verzweigungsgrad von t = 1024 benötigt ein B-Baum damit Zugriffe auf zehn mal weniger Knoten zum Auffinden eines Datenelements. Wenn der Zugriff auf einen Knoten die Dauer der gesamten Operation dominiert (wie das beim Zugriff auf Hintergrundspeicher der Fall ist), ergibt sich dadurch eine zehnfach erhöhte Ausführungsgeschwindigkeit.

Spezialfälle und Varianten
Für den Spezialfall t=2 spricht man von 2-3-4-Baum 2-3-4-Bäumen, da Knoten in einem solchen Baum 2, 3, oder 4 Kinder haben können. Varianten des B-Baumes sind B+-Baum B+-Bäume und B*-Baum B*-Bäume.

Operationen


Suchen
Die Suche nach einem Schlüssel k liefert denjenigen Knoten x, der diesen Schlüssel speichert, und die Position i innerhalb dieses Knotens, für die gilt, dass k = x.k_i. Enthält der Baum den Schlüssel k nicht, liefert die Suche das Ergebnis ''nicht enthalten''. Die Suche läuft in folgenden Schritten ab: # Die Suche beginnt mit dem Wurzelknoten r als aktuellem Knoten x . # Ist x ein innerer Knoten, #* wird die Position j des kleinsten Schlüssels bestimmt, der größer oder gleich k ist. #* Existiert eine solche Position j, #** aber ist k \neq x.k_j, kann der gesuchte Schlüssel nur in dem Unterbaum mit Wurzel x.c_j enthalten sein. Die Suche wird daher mit Schritt 2 und dem Knoten x.c_j als aktuellem Knoten fortgesetzt. #** ansonsten wurde der Schlüssel gefunden und (x, j) wird als Ergebnis zurückgeliefert. #* Existiert keine solche Position, ist der Schlüssel größer als alle im aktuellen Knoten gespeicherten Schlüssel. In diesem Fall kann der gesuchte Schlüssel nur noch in dem Unterbaum enthalten sein, auf den der letzte Kindverweis x.c_{x.s+1} zeigt. In diesem Fall wird die Suche mit Schritt 2 und dem Knoten x.c_{x.s+1} als aktuellem Knoten fortgesetzt. # Ist x ein Blattknoten, #* Wird k in den Schlüsseln von x gesucht. #* Wenn der Schlüssel an Position j gefunden wird, ist das Ergebnis (x, j), ansonsten ''nicht enthalten''. Bild:B-tree-search.png thumb|320px|Abbildung 2: Suche im B-Baum In nebenstehender Abbildung ist die Situation während der Suche nach dem Schlüssel k = 9 dargestellt. Im Schritt 2 aus obigem Algorithmus wird im aktuellen Knoten x die kleinste Position j gesucht, für die 9 \leq x.k_j gilt. Im konkreten Beispiel wird die Position 2 gefunden, da 5 \leq 9 \leq 13 gilt. Die Suche wird daher im rot markierten Unterbaum x.c_2 fortgesetzt, weil sich aufgrund der B-Baum-Eigenschaft (2) der gesuchte Schlüssel 9 nur in diesem Unterbaum befinden kann.

Einfügen
Bild:B-tree-splitt.png thumb|320px|right|Abbildung 3: Teilen eines vollen B-Baum-Knotens. Das Einfügen eines Schlüssels k in einen B-Baum geschieht immer in einem Blattknoten. # In einem vorbereitenden Schritt wird der Blattknoten x_\mathrm{insert} gesucht, in den eingefügt werden muss. Dabei werden Vorkehrungen getroffen, damit die Einfügeoperation nicht die B-Baum-Bedingungen verletzt und einen Knoten erzeugt, der mehr als 2t-1 Schlüssel enthält. #In einem abschließenden Schritt wird k unter Berücksichtigung der Sortierreihenfolge lokal in x eingefügt. Die Suche von x_\mathrm{insert} läuft mit zwei Unterschieden so ab, wie unter #Suchen Suchen beschrieben. Diese Unterschiede sind: * Die Suche bricht nicht in einem inneren Knoten ab, wenn dort der Schlüssel k bereits gefunden wird. Es findet immer ein Abstieg zu einem Blattknoten statt. * Bevor die Suche zu einem Kindknoten x.c_j absteigt, wird überprüft, ob x.c_j voll ist, d. h. bereits 2t-1 Schlüssel enthält. In diesem Fall wird x.c_j vorsorglich geteilt. Dies garantiert, dass die Einfügeoperation mit einem einzigen Baumabstieg durchgeführt werden kann und keine anschließenden Reparaturmaßnahmen zur Wiederherstellung der B-Baum-Bedingungen durchgeführt werden müssen. Das Teilen eines vollen Baumknotens geschieht wie in Abbildung 3 gezeigt. Die Suche ist an Knoten x angekommen und würde zum Kindknoten x.c_2 absteigen (roter Pfeil). Das heißt, die Suchposition ist j = 2. Da dieser Kindknoten voll ist, muss er vor dem Abstieg geteilt werden, um zu garantieren, dass eine Einfügung möglich ist. Ein voller Knoten hat mit 2t-1 immer eine ungerade Anzahl von Schlüsseln. Der mittlere davon (in der Abbildung ist das Schlüssel x.c_2.k_3) wird im aktuellen Knoten an der Suchposition j eingefügt. Der Knoten x.c_2 wird in zwei gleich große Knoten mit jeweils t-1 Schlüsseln geteilt und diese über die beiden neuen Zeigerpositionen verlinkt (zwei rote Pfeile im Ergebnis). Die Suche steigt anschließend entweder in den Unterbaum x.c_2 oder x.c_3 ab, je nachdem, ob der einzufügende Schlüssel kleinergleich dem mittleren Schlüssel des geteilten Knotens ist oder nicht.

Löschen
Das Löschen eines Schlüssels k_\mathrm{delete} ist eine komplexere Operation als das Einfügen, da hier auch der Fall betrachtet werden muss, dass ein Schlüssel aus einem inneren Knoten gelöscht wird. Der Ablauf ist dabei wie beim Suchen nach dem zu löschenden Schlüssel k_\mathrm{delete} mit dem Unterschied, dass vor dem Abstieg in einen Unterbaum überprüft wird, ob dieser genügend Schlüssel (\geq t) enthält, um eine eventuelle Löschoperation ohne Verletzung der B-Baum-Bedingungen durchführen zu können. Dieses Vorgehen ist analog zum Einfügen und vermeidet anschließende Reparaturmaßnahmen. Enthält der Unterbaum, den die Suche für den Abstieg auswählt, die minimale Anzahl von Schlüsseln (t-1), wird entweder eine #Verschiebung Verschiebung oder eine #Verschmelzung Verschmelzung durchgeführt. Wird der gesuchte Schlüssel in einem Blattknoten gefunden, kann er dort direkt gelöscht werden. Wird er dagegen in einem inneren Knoten gefunden, passiert die Löschung wie in #Löschen aus inneren Knoten Löschen aus inneren Knoten beschrieben.

= Verschiebung
= Bild:B-tree-move.png thumb|320px|right|Abbildung 4: Verschieben eines Schlüssels im B-Baum. Enthält der für den Abstieg ausgewählte Unterbaum nur die minimale Schlüsselanzahl t-1, aber ein vorausgehender oder nachfolgender Geschwisterknoten hat mindestens t Schlüssel, wird ein Schlüssel in den ausgewählten Knoten verschoben, wie in nebenstehender Abbildung gezeigt. Die Suche hat hier x.c_2 für den Abstieg ausgewählt (da x.k_1 < k_\mathrm{delete} < k_2), dieser Knoten enthält aber nur t-1 Schlüssel (roter Pfeil). Da der nachfolgende Geschwisterknoten x.c_3 ausreichend viele Schlüssel enthält, kann von dort der kleinste Schüssel x.c_3.k_1 in den Vaterknoten verschoben werden, um im Gegenzug den Schlüssel x.k_2 als zusätzlichen Schlüssel in den für den Abstieg ausgewählten Knoten zu verschieben. Dazu wird der linke Unterbaum von x.c_3.k_1 zum neuen rechten Unterbaum des verschobenen Schlüssels x.k_2. Man kann sich leicht davon überzeugen, dass diese ''Rotation'' die Sortierungsbedingungen erhält, da für alle Schlüssel k im verschobenen Unterbaum vor und nach der Verschiebung die Forderung x.k_2 \leq k \leq x.c_3.k_1 gilt. Eine symmetrische Operation kann zur Verschiebung eines Schlüssels aus einem vorausgehenden Geschwisterknoten durchgeführt werden.

= Verschmelzung
= Bild:B-tree-join.png thumb|320px|right|Abbildung 5: Verschmelzen zweier B-Baum Kindknoten. Enthalten sowohl der für den Abstieg ausgewählte Unterbaum x.c_2 als auch sein unmittelbar vorausgehender und nachfolgender Geschwisterknoten genau die minimale Schlüsselanzahl, ist eine #Verschiebung Verschiebung nicht möglich. In diesem Fall wird eine Verschmelzung des ausgewählten Unterbaumes mit dem vorausgehenden oder nachfolgenden Geschwisterknoten gemäß nebenstehender Abbildung durchgeführt. Dazu wird der Schlüssel aus dem Vaterknoten x, welcher die Wertebereiche der Schlüssel in den beiden zu verschmelzenden Knoten trennt, als mittlerer Schlüssel in den verschmolzenen Knoten verschoben. Die beiden Verweise auf die jetzt verschmolzenen Kindknoten werden durch einen Verweis auf den neuen Knoten ersetzt. Da der Algorithmus vor dem Abstieg in einen Knoten sicherstellt, dass dieser mindestens t anstelle der von den B-Baum-Bedingungen geforderten t-1 Schlüssel enthält, ist gewährleistet, dass der Vaterknoten x eine ausreichende Schlüsselanzahl enthält, um einen Schlüssel für die Verschmelzung zur Verfügung zu stellen. Nur im Fall, dass zwei Kinder des Wurzelknotens verschmolzen werden, kann diese Bedingung verletzt sein, da die Suche bei diesem Knoten beginnt. Die B-Baum-Bedingungen fordern für den Wurzelknoten mindestens einen Schlüssel, wenn der Baum nicht leer ist. Bei Verschmelzung der letzten zwei Kinder des Wurzelknotens, wird aber sein letzter Schlüssel in das neu entstehende einzige Kind verschoben, was zu einem leeren Wurzelknoten in einem nicht leeren Baum führt. In diesem Fall wird der leere Wurzelknoten gelöscht und durch sein einziges Kind ersetzt.

= Löschen aus inneren Knoten
= Bild:B-tree-delete.png thumb|320px|right|Abbildung 6: Löschen eines Schlüssels aus einem inneren Knoten. Wird der zu löschende Schlüssel k_\mathrm{delete} bereits in einem inneren Knoten gefunden (k_\mathrm{delete} = x.k_2 in nebenstehender Abbildung), kann dieser nicht direkt gelöscht werden, weil er für die Trennung der Wertebereiche seiner beiden Unterbäume x.c_2 und x.c_3 benötigt wird. In diesem Fall wird sein symmetrischer Vorgänger (oder sein symmetrischer Nachfolger) gelöscht und an seine Stelle kopiert. Der symmetrische Vorgänger ist der größte Blattknoten im linken Unterbaum x.c_2, befindet sich also dort ganz rechts außen. Der symmetrische Nachfolger ist entsprechend der kleinste Blattknoten im rechten Unterbaum x.c_3 und befindet sich dort ganz links außen. Die Entscheidung, in welchen Unterbaum der Abstieg für die Löschung stattfindet, wird davon abhängig gemacht, welcher genügend Schlüssel enthält. Haben beide nur die minimale Schlüsselanzahl, werden die Unterbäume verschmolzen und anschließend die Löschung im neu entstandenen Kindknoten durchgeführt.

Beispiel
Bild:B-tree-aggregated-example.png thumb|320px|Abbildung 7: Evolution eines B-Baumes Nebenstehende Abbildung zeigt die Entwicklung eines B-Baumes mit minimalem Verzweigungsgrad t=2. Knoten in einem solchen Baum können minimal einen und maximal drei Schlüssel speichern und haben zwischen zwei und vier Verweisen auf Kindknoten. Man spricht daher auch von einem 2-3-4-Baum. In einer praktischen Anwendung würde man dagegen einen B-Baum mit wesentlich größerem Verzweigungsgrad verwenden. Folgende Operationen wurden auf einem 2-3 Baum (siehe Abbildung rechts) durchgeführt: * a–c) Einfügen von 5, 13 und 27 in einen anfangs leeren Baum. * d–e) Einfügen von 9 führt zum Teilen des Wurzelknotens. * f) Einfügen von 7 in einen Blattknoten. * g–h) Einfügen von 3 führt zum Teilen eines Knotens. * i–j) Um 9 löschen zu können, wird ein Schlüssel aus einem Geschwisterknoten verschoben. * k–l) Das Löschen von 7 führt zum Verschmelzen von zwei Knoten. * m) Löschen von 5 aus einem Blatt. * n–q) Löschen von 3 führt zur Verschmelzung der letzten zwei Kinder des Wurzelknotens. Der entstehende leere Wurzelknoten wird durch sein einziges Kind ersetzt.

Siehe auch
* R-Baum ist ein verwandtes Indexverfahren für mehrdimensionale Daten. * B+-Baum B+-Baum und B*-Baum sind B-Baum-Varianten. * 2-3-4-Baum ist ein Spezialfall eines B-Baumes mit minimalem Verzweigungsgrad t=2. * AVL-Baum * Rot-Schwarz-Baum

Literatur
''deutsch'' * Niklaus Wirth: ''Algorithmen und Datenstrukturen mit Modula-2'', Stuttgart 1986, ISBN 3519022605 ''englisch'' * R. Bayer, E. McCreight: ''Organization and Maintenance of Large Ordered Indexes''. In: ''Acta Informatica 1'', 1972, S. 173–189 * R. Bayer, E. McCreight: ''Symmetric binary B-Trees: data structure and maintenance algorithms''. In: ''Acta Informatica 1'', 1972, S. 290–306

Weblinks
Tools zum Ausprobieren von B-Bäumen:
http://slady.net/java/bt – B-Baum Java Applet
- http://www.fh-augsburg.de/~mweiss/applets/bTree.shower2.html – Java Applet
http://www.engin.umd.umich.edu/CIS/course.des/cis350/treetool/ (produziert teilweise abweichende Ergebnisse zu der anderen Alternative) Erklärung mit Beispielen:
http://www.rz.rwth-aachen.de/mata/downloads/algo_dat/folien2006/AlgoDat2006_Teil10.pdf {{Lesenswert}} Kategorie:Suchbaum Kategorie:Datenbank cs:B-strom en:B-tree es:?rbol-B fr:Arbre B it:B-Albero ja:B木 ko:B 트리 lt:B-medis pl:B-drzewo pt:?rvore B sr:Б-?табло sv:B-träd zh:B树

*** Shopping-Tipp: B-Baum




[Der Artikel zu B-Baum stammt aus dem Nachschlagewerk Wikipedia, der freien Enzyklopädie. Dort findet sich neben einer Übersicht der Autoren die Möglichkeit, den Original-Text des Artikels B-Baum zu editieren.
Die Texte von Wikipedia und dieser Seite stehen unter der GNU Free Documentation License.]

<<Zurück | Zur Startseite | Impressum | Zum Beginn dieser Seite