In der Informatik ist ein B-Baum eine Baumdatenstruktur, die Daten sortiert hält und Suchen, folgenden Zugang, Einfügungen und Auswischen in der logarithmischen Zeit erlaubt. Der B-Baum ist eine Generalisation eines binären Suchbaums, in dem ein Knoten mehr als zwei Kinder haben kann. Verschieden vom Selbstausgleichen binärer Suchbäume wird der B-Baum für Systeme optimiert, die lesen und große Datenblocks schreiben. Es wird in Datenbanken und filesystems allgemein verwendet.

Übersicht

In B-Bäumen inner (Nichtblatt) können Knoten eine variable Zahl von Kinderknoten innerhalb von einer vorherbestimmten Reihe haben. Wenn Daten eingefügt oder von einem Knoten, seiner Zahl von Kinderknotenänderungen entfernt werden. Um die vorherbestimmte Reihe aufrechtzuerhalten, können innere Knoten angeschlossen oder gespalten werden. Weil eine Reihe von Kinderknoten erlaubt wird, brauchen B-Bäume das Wiederausgleichen so oft nicht wie andere selbstbalancierende Suchbäume, aber können einen Raum vergeuden, da Knoten nicht völlig voll sind. Die niedrigeren und oberen Grenzen auf der Zahl von Kinderknoten werden normalerweise für eine besondere Durchführung befestigt. Zum Beispiel, in einem 2-3 B-Baum (häufig einfach gekennzeichnet als ein 2-3 Baum), kann jeder innere Knoten nur 2 oder 3 Kinderknoten haben.

Jeder innere Knoten eines B-Baums wird mehrere Schlüssel enthalten. Gewöhnlich wird die Zahl von Schlüsseln gewählt, um sich zwischen zu ändern, und. In der Praxis nehmen die Schlüssel den am meisten Raum-in einem Knoten auf. Der Faktor 2 wird versichern, dass Knoten gespalten oder verbunden werden können. Wenn ein innerer Knoten Schlüssel hat, dann kann das Hinzufügen eines Schlüssels zu diesem Knoten durch das Aufspalten des Schlüsselknotens in zwei Schlüsselknoten und das Hinzufügen des Schlüssels zum Elternteilknoten vollbracht werden. Jeder Spalt-Knoten hat die erforderliche minimale Zahl von Schlüsseln. Ähnlich, wenn ein innerer Knoten und sein Nachbar jeder hat Schlüssel, dann kann ein Schlüssel vom inneren Knoten durch das Kombinieren mit seinem Nachbar gelöscht werden. Das Löschen des Schlüssels würde den inneren Knoten Schlüssel haben lassen; das Verbinden dem Nachbar würde Schlüssel plus ein mehr vom Elternteil des Nachbars heruntergebrachter Schlüssel hinzufügen. Das Ergebnis ist ein völlig voller Knoten von Schlüsseln.

Die Zahl von Zweigen (oder Kinderknoten) von einem Knoten wird ein mehr sein als die Zahl von im Knoten versorgten Schlüsseln. In einem 2-3 B-Baum werden die inneren Knoten jeden einen Schlüssel (mit zwei Kinderknoten) oder zwei Schlüsseln (mit drei Kinderknoten) versorgen. Ein B-Baum wird manchmal mit den Rahmen — oder einfach mit der höchsten sich verzweigenden Ordnung beschrieben.

Ein B-Baum wird erwogen durch das Verlangen dass alle Blatt-Knoten behalten, an derselben Tiefe sein. Diese Tiefe wird langsam zunehmen, weil Elemente zum Baum hinzugefügt werden, aber eine Zunahme in der gesamten Tiefe ist selten, und läuft auf alle Blatt-Knoten hinaus, die ein mehr Knoten weiter weg von der Wurzel sind.

B-Bäume sind im Vorteil gegenüber alternativen Durchführungen, wenn Knotenzugriffszeiten weit Zugriffszeiten innerhalb von Knoten überschreiten, weil dann die Kosten, auf den Knoten zuzugreifen, über vielfache Operationen innerhalb des Knotens amortisiert werden können. Das kommt gewöhnlich vor, wenn die Knoten in der sekundären Lagerung wie Laufwerke sind. Durch die Maximierung der Zahl von Kinderknoten innerhalb jedes inneren Knotens, der Höhe der Baumabnahmen und der Zahl von teuren Knotenzugängen wird reduziert. Außerdem kommt das Wiederausgleichen des Baums weniger häufig vor. Die maximale Zahl von Kinderknoten hängt von der Information ab, die für jeden Kinderknoten und die Größe eines vollen Plattenblocks oder eine analoge Größe in der sekundären Lagerung versorgt werden muss. Während 2-3 B-Bäume leichter sind zu erklären, wollen praktische B-Bäume mit der sekundären Lagerung, dass eine Vielzahl von Kinderknoten Leistung verbessert.

Varianten

Der Begriff B-Baum kann sich auf ein spezifisches Design beziehen, oder es kann sich auf eine allgemeine Klasse von Designs beziehen. Im engeren Sinn versorgt ein B-Baum Schlüssel in seinen inneren Knoten, aber braucht jene Schlüssel in den Aufzeichnungen an den Blättern nicht zu versorgen. Die allgemeine Klasse schließt Schwankungen wie der B-Baum und der B-Baum ein.

• Im B-Baum werden Kopien der Schlüssel in den inneren Knoten versorgt; die Schlüssel und Aufzeichnungen werden in Blättern versorgt; außerdem kann ein Blatt-Knoten einen Zeigestock zum folgenden Blatt-Knoten einschließen, um folgenden Zugang zu beschleunigen.
• Der B-Baum erwägt mehr benachbarte innere Knoten, um die inneren Knoten dichter gepackt zu halten. Diese Variante verlangt, dass Nichtwurzelknoten mindestens 2/3 voll statt 1/2 sind. Um das aufrechtzuerhalten, anstatt einen Knoten sofort aufzuteilen, wenn es voll wird, werden seine Schlüssel mit einem Knoten daneben geteilt. Wenn beide Knoten dann voll sind, werden die zwei Knoten in drei gespalten.
• Aufgezählter B-Baumladen, mit jedem Zeigestock innerhalb des Baums, der Zahl von Knoten im Subbaum unter diesem Zeigestock. Das erlaubt schnelle Suchen nach der N-ten Aufzeichnung in der Schlüsselordnung oder dem Zählen der Zahl von Aufzeichnungen zwischen irgendwelchen zwei Aufzeichnungen und verschiedenen anderen zusammenhängenden Operationen.

Unbekannte Etymologie

Rudolf Bayer und Ed McCreight haben den B-Baum erfunden, während sie an Boeing Research Labs 1971 gearbeitet haben, aber sie haben nicht erklärt, was, wenn irgendetwas der B eintritt. Douglas Comer erklärt:

Donald Knuth sinnt über die Etymologie von B-Bäumen in seinem Vortrag im Mai 1980 auf dem Thema "CS144C Klassenzimmer-Vortrag über die Plattenlagerung und B-Bäume" nach, vorschlagend, dass der "B" aus Boeing oder aus dem Namen von Bayer entstanden sein kann.

Das Datenbankproblem

Zeit, um eine sortierte Datei zu suchen

Gewöhnlich sind das Sortieren und die Suche von Algorithmen durch die Zahl von Vergleich-Operationen charakterisiert worden, die mit der Ordnungsnotation durchgeführt werden müssen. Eine binäre Suche eines sortierten Tisches mit Aufzeichnungen kann zum Beispiel in Vergleichen getan werden. Wenn der Tisch 1,000,000 Aufzeichnungen hatte, dann konnte eine spezifische Aufzeichnung mit ungefähr 20 Vergleichen gelegen werden:.

Große Datenbanken sind auf Laufwerken historisch behalten worden. Die Zeit, um eine Aufzeichnung auf einem Laufwerk zu lesen, kann vorherrschen die Zeit musste Schlüssel vergleichen, sobald die Aufzeichnung verfügbar ist. Die Zeit, um eine Aufzeichnung von einem Laufwerk zu lesen, schließt eine Positionierungszeit und eine Rotationsverzögerung ein. Die Positionierungszeit kann 0 zu 20 oder mehr Millisekunden, und die Rotationsverzögerungsdurchschnitte ungefähr Hälfte der Folge-Periode sein. Für 7200 RPM Drive ist die Folge-Periode 8.33 Millisekunden. Für einen Laufwerk wie der Seagate ST3500320NS ist die Positionierungszeit der Spur-zu-spurig 0.8 Millisekunden, und die durchschnittliche Lesen-Positionierungszeit ist 8.5 Millisekunden. Für die Einfachheit, nehmen Sie an, dass das Lesen von der Platte ungefähr 10 Millisekunden nimmt.

Naiv, dann, würde die Zeit, um eine Aufzeichnung aus einer Million ausfindig zu machen, 20 Platte nehmen liest Zeiten gelesene 10 Millisekunden pro Platte, der 0.2 Sekunden ist.

Die Zeit wird so nicht schlecht sein, weil individuelle Aufzeichnungen zusammen in einem Plattenblock gruppiert werden. Ein Plattenblock könnte 16 Kilobytes sein. Wenn jede Aufzeichnung 160 Bytes ist, dann konnten 100 Aufzeichnungen in jedem Block versorgt werden. Die Platte hat Zeit oben gelesen war wirklich für einen kompletten Block. Sobald der Plattenkopf in der Position ist, können ein oder mehr Plattenblöcke mit wenig Verzögerung gelesen werden. Mit 100 Aufzeichnungen pro Block brauchen die letzten ungefähr 6 Vergleiche nicht zu tun jede Platte liest — die Vergleiche sind alle innerhalb des letzten gelesenen Plattenblocks.

Um die Suche weiter zu beschleunigen, müssen die ersten 13 bis 14 Vergleiche (der jeder einen Plattenzugang verlangt hat) beschleunigt werden.

Ein Index beschleunigt die Suche

Eine bedeutende Verbesserung kann mit einem Index gebildet werden. Im Beispiel oben liest anfängliche Platte hat die Suchreihe durch einen Faktor zwei eingeengt. Das kann wesentlich durch das Schaffen eines Hilfsindex verbessert werden, der die erste Aufzeichnung in jedem Plattenblock enthält (manchmal hat einen spärlichen Index genannt). Dieser Hilfsindex würde 1 % der Größe der ursprünglichen Datenbank sein, aber es kann schneller gesucht werden. Die Entdeckung eines Zugangs im Hilfsindex würde uns der Block erzählen, in der Hauptdatenbank zu suchen; nach der Suche des Hilfsindex würden wir nur dass ein Block der Hauptdatenbank — zu einem Selbstkostenpreis von eine mehr gelesene Platte suchen müssen. Der Index würde 10,000 Einträge halten, so würde man höchstens 14 Vergleiche brauchen. Wie die Hauptdatenbank würden die letzten ungefähr 6 Vergleiche im aux Index auf demselben Plattenblock sein. Der Index konnte in ungefähr 8 Platte gesucht werden liest, und auf die gewünschte Aufzeichnung konnte in 9 Platte zugegriffen werden liest.

Der Trick, einen Hilfsindex zu schaffen, kann wiederholt werden, um einen Hilfsindex zum Hilfsindex zu machen. Das würde einen aux-aux Index machen, der nur 100 Einträge brauchen würde und einen Plattenblock einfügen würde.

Anstatt 14 Plattenblöcke zu lesen, um die gewünschte Aufzeichnung zu finden, müssen wir nur 3 Blöcke lesen. Wenn er liest und das erste (und nur) sucht, identifiziert der Block des aux-aux Index den relevanten Block im Aux-Index. Das Lesen und die Suche dieses Aux-Index-Blocks identifizieren den relevanten Block in der Hauptdatenbank. Statt 150 Millisekunden brauchen wir nur 30 Millisekunden, um die Aufzeichnung zu bekommen.

Die Hilfsindizes haben das Suchproblem von einer binären Suche gedreht, die grob verlangt, dass Platte zu einem verlangendem liest, liest nur Platte, wo der blockierende Faktor ist (die Zahl von Einträgen pro Block: Einträge pro Block; liest).

In der Praxis, wenn die Hauptdatenbank oft gesucht wird, können der aux-aux Index und viel vom aux Index in einem geheimen Plattenlager wohnen, so würden sie keine gelesene Platte übernehmen.

Einfügungen und Auswischen verursachen Schwierigkeiten

Wenn sich die Datenbank nicht ändert, dann ist das Kompilieren des Index einfach zu tun, und der Index braucht nie geändert zu werden. Wenn es Änderungen gibt, dann wird das Handhaben der Datenbank und seines Index mehr kompliziert.

Das Löschen von Aufzeichnungen von einer Datenbank verursacht viel Schwierigkeiten nicht. Der Index kann dasselbe bleiben, und die Aufzeichnung kann gerade, wie gelöscht, gekennzeichnet werden. Die Datenbank bleibt in der sortierten Ordnung. Wenn es viel Auswischen gibt, dann werden die Suche und Lagerung weniger effizient.

Einfügungen sind eine Katastrophe in einer sortierten folgenden Datei, weil der Platz für die eingefügte Aufzeichnung gemacht werden muss. Wenn sie eine Aufzeichnung bevor einfügt, verlangt die erste Aufzeichnung in der Datei Verschiebung von allen Aufzeichnungen unten ein. Solch eine Operation ist gerade zu teuer, um praktisch zu sein.

Ein Trick soll einen Raum verlassen, der herumliegt, um für Einfügungen verwendet zu werden. Anstatt alle Aufzeichnungen in einem Block dicht zu versorgen, kann der Block einen freien Raum haben, um nachfolgende Einfügungen zu berücksichtigen. Jene Aufzeichnungen würden gekennzeichnet, als ob sie Aufzeichnungen "gelöscht" wurden.

Jetzt sind sowohl Einfügungen als auch Auswischen schnell, so lange Raum auf einem Block verfügbar ist. Wenn eine Einfügung unterm Hammer nicht passen wird, dann muss ein freier Raum auf einem nahe gelegenen Block gefunden werden, und die Hilfsindizes angepasst. Die Hoffnung ist genug Raum ist nahe gelegen, dass viele Blöcke nicht reorganisiert zu werden brauchen. Wechselweise können einige Plattenblöcke aus der Folge verwendet werden.

Der B-Baum verwendet alle jene Ideen

Der B-Baum verwendet alle obengenannten Ideen:

• Es behält Aufzeichnungen in der sortierten Ordnung für das folgende Überqueren
• Es verwendet einen hierarchischen Index, um die Zahl der Platte zu minimieren, liest
• Es verwendet teilweise volle Blöcke, um Einfügungen und Auswischen zu beschleunigen
• Der Index wird mit einem rekursiven Algorithmus elegant angepasst

Außerdem minimiert ein B-Baum Verschwendung durch das Sicherstellen, dass die Innenknoten mindestens ½ voll sind. Ein B-Baum kann eine beliebige Zahl von Einfügungen und Auswischen behandeln.

Technische Beschreibung

Fachsprache

Leider ist die Literatur auf B-Bäumen in seinem Gebrauch von Begriffen in Zusammenhang mit B-Bäumen nicht gleichförmig.

, und andere definieren die Ordnung des B-Baums als die minimale Zahl von Schlüsseln in einem Nichtwurzelknoten. weist darauf hin, dass Fachsprache zweideutig ist, weil die maximale Zahl von Schlüsseln nicht klar ist. Ein Auftrag 3 B-Baum könnte ein Maximum von 6 Schlüsseln oder ein Maximum von 7 Schlüsseln halten. vermeidet das Problem durch das Definieren der Ordnung, maximale Zahl von Kindern zu sein (der ein mehr ist als die maximale Zahl von Schlüsseln).

Der Begriff Blatt ist auch inkonsequent. betrachtet als das Blatt-Niveau, um der Tiefststand von Schlüsseln, aber Knuth zu sein, hat gedacht, dass das Blatt-Niveau ein Niveau unter den niedrigsten Schlüsseln war. Es gibt viele mögliche Durchführungswahlen. In einigen Designs können die Blätter die komplette Datenaufzeichnung halten; in anderen Designs können die Blätter nur Zeigestöcke zur Datenaufzeichnung halten. Jene Wahlen sind für die Idee von einem B-Baum nicht grundsätzlich.

Es gibt auch unglückliche Wahlen wie das Verwenden der Variable k, um die Zahl von Kindern zu vertreten, als k mit der Zahl von Schlüsseln verwirrt sein konnte.

Für die Einfachheit nehmen die meisten Autoren an, dass es eine festgelegte Zahl von Schlüsseln gibt, die einen Knoten einfügen. Die grundlegende Annahme ist die Schlüsselgröße wird befestigt, und die Knotengröße wird befestigt. In der Praxis können Schlüssel der variablen Länge verwendet werden.

Definition

Gemäß der Definition von Knuth, einem B-Baum der Ordnung ist M (die maximale Zahl von Kindern für jeden Knoten) ein Baum, der die folgenden Eigenschaften befriedigt:

1. Jeder Knoten hat am grössten Teil der M Kinder.
2. Jeder Knoten (außer der Wurzel) hat mindestens ⌈⌉ Kinder.
3. Die Wurzel hat mindestens zwei Kinder, wenn es nicht ein Blatt-Knoten ist.
4. Ein Nichtblatt-Knoten mit k Kindern enthält k1 Schlüssel.
5. Alle Blätter erscheinen in demselben Niveau, und tragen Information.

Die Elemente jedes inneren Knotens handeln als Trennungswerte, die seine Subbäume teilen. Zum Beispiel, wenn ein innerer Knoten 3 Kinderknoten (oder Subbäume) dann hat, muss er 2 Trennungswerte oder Elemente haben: a und a. Alle Werte im leftmost Subbaum werden weniger sein als a, alle Werte im mittleren Subbaum werden zwischen a und a sein, und alle Werte im niedrigstwertigen Subbaum werden größer sein als a.

Innere Knoten

: Innere Knoten sind alle Knoten abgesehen von Blatt-Knoten und dem Wurzelknoten. Sie werden gewöhnlich als ein bestellter Satz von Elementen und Kinderzeigestöcken vertreten. Jeder innere Knoten enthält ein Maximum von U Kindern und ein Minimum von L Kindern. So ist die Zahl der Elemente immer 1 weniger als die Zahl von Kinderzeigestöcken (die Zahl der Elemente ist zwischen L1 und U1). U muss entweder 2L oder 2L1 sein; deshalb ist jeder innere Knoten mindestens halb voll. Die Beziehung zwischen U und L deutet an, dass zwei halb volle Knoten angeschlossen werden können, um einen gesetzlichen Knoten zu machen, und ein voller Knoten in zwei gesetzliche Knoten gespalten werden kann (wenn es Zimmer gibt, um ein Element in den Elternteil hochzuschieben). Diese Eigenschaften machen es möglich, neue Werte in einen B-Baum zu löschen und einzufügen und den Baum anzupassen, um die B-Baumeigenschaften zu bewahren.

Der Wurzelknoten

: Die Wurzelknotenzahl von Kindern hat dieselbe obere Grenze wie innere Knoten, aber hat keine niedrigere Grenze. Zum Beispiel, wenn es weniger gibt als L1 Elemente im kompletten Baum, wird die Wurzel der einzige Knoten im Baum ohne Kinder überhaupt sein.

Blatt-Knoten

: Blatt-Knoten haben dieselbe Beschränkung der Zahl der Elemente, aber haben keine Kinder und keine Kinderzeigestöcke.

Ein B-Baum der Tiefe n+1 kann über U Zeiten so viele Sachen halten wie ein B-Baum der Tiefe n, aber die Kosten der Suche, einfügen, und Operationen löschen wächst mit der Tiefe des Baums. Als mit jedem erwogenen Baum wachsen die Kosten viel langsamer als die Zahl der Elemente.

Ein erwogener Baumladen schätzt nur auf Blatt-Knoten, und verwenden Sie verschiedene Arten von Knoten für Blatt-Knoten und innere Knoten. B-Bäume behalten Werte in jedem Knoten im Baum, und können dieselbe Struktur für alle Knoten verwenden. Jedoch, da Blatt-Knoten nie Kinder, der B-Baumvorteil der verbesserten Leistung haben, wenn sie eine Spezialstruktur verwenden.

Bester Fall und Grenzfall-Höhen

Lassen Sie h die Höhe des klassischen B-Baums sein. Lassen Sie n> 0 die Zahl von Einträgen im Baum sein. Lassen Sie M die maximale Zahl von Kindern sein, die ein Knoten haben kann. Jeder Knoten kann an den meisten m1 Schlüsseln haben.

Die beste Fall-Höhe eines B-Baums ist:

:

Lassen Sie d die minimale Zahl von Kindern ein innerer (Nichtwurzel) sein Knoten kann haben. Für einen gewöhnlichen B-Baum, d =  M/2 .

Die Grenzfall-Höhe eines B-Baums ist:

:

und geben Sie einen ein bisschen verschiedenen Ausdruck für die Grenzfall-Höhe (vielleicht, weil, wie man betrachtet, der Wurzelknoten Höhe 0 hat).

:

Algorithmen

Suchen

Suche ist der Suche eines binären Suchbaums ähnlich. An der Wurzel anfangend, wird der Baum von oben bis unten rekursiv überquert. An jedem Niveau wählt die Suche den Kinderzeigestock (Subbaum), dessen Trennungswerte auf beiden Seiten des Suchwerts sind.

Binäre Suche ist normalerweise (aber nicht notwendigerweise) verwendet innerhalb von Knoten, um die Trennungswerte und den Kinderbaum von Interesse zu finden.

Einfügung

Alle Einfügungen fangen an einem Blatt-Knoten an. Um ein neues Element einzufügen, suchen Sie den Baum, um den Blatt-Knoten zu finden, wo das neue Element hinzugefügt werden sollte. Fügen Sie das neue Element in diesen Knoten mit den folgenden Schritten ein:

1. Wenn der Knoten weniger enthält als die maximale gesetzliche Zahl der Elemente, dann gibt es Zimmer für das neue Element. Fügen Sie das neue Element in den Knoten ein, die Elemente des Knotens bestellt haltend.
2. Sonst ist der Knoten voll, spalten Sie ihn gleichmäßig in zwei Knoten so:
3. Eine einzelne Mittellinie wird aus der Zahl von den Elementen des Blattes und dem neuen Element gewählt.
4. Werte weniger als die Mittellinie werden im neuen linken Knoten und den größeren Werten gelegt, als die Mittellinie im neuen richtigen Knoten mit der Mittellinie gestellt wird, die als ein Trennungswert handelt.
5. Der Trennungswert wird in den Elternteil des Knotens eingefügt, der ihn veranlassen kann, und so weiter gespalten zu werden. Wenn der Knoten keinen Elternteil hat (d. h. der Knoten war die Wurzel), schaffen Sie eine neue Wurzel über diesem Knoten (die Höhe des Baums vergrößernd).

Wenn das Aufspalten den ganzen Weg bis zur Wurzel geht, schafft es eine neue Wurzel mit einem einzelnen Separator-Wert und zwei Kindern, der ist, warum tiefer gebunden die Größe von inneren Knoten für die Wurzel nicht gilt. Die maximale Zahl der Elemente pro Knoten ist U1. Wenn ein Knoten gespalten wird, bewegt sich ein Element dem Elternteil, aber ein Element wird hinzugefügt. Also, es muss möglich sein, die maximale Nummer U1 von Elementen in zwei gesetzliche Knoten zu teilen. Wenn diese Zahl seltsam ist, dann enthalten U=2L und einer der neuen Knoten (U2)/2 = L1 Elemente, und sind folglich ein gesetzlicher Knoten, und der andere enthält ein mehr Element, und folglich ist es auch gesetzlich. Wenn U1 sogar, dann U=2L1 ist, also gibt es 2L2 Elemente im Knoten. Die Hälfte dieser Zahl ist L1, der die minimale pro Knoten erlaubte Zahl der Elemente ist.

Ein verbesserter Algorithmus unterstützt einen einzelnen Pass unten der Baum von der Wurzel bis den Knoten, wo die Einfügung stattfinden wird, irgendwelche vollen Knoten gestoßen unterwegs spaltend. Das verhindert das Bedürfnis, die Elternteilknoten ins Gedächtnis zurückzurufen, das teuer sein kann, wenn die Knoten auf der sekundären Lagerung sind. Jedoch, um diesen verbesserten Algorithmus zu verwenden, müssen wir im Stande sein, ein Element dem Elternteil zu senden und die restlichen U2 Elemente in zwei gesetzliche Knoten zu spalten, ohne ein neues Element hinzuzufügen. Das verlangt U = 2L aber nicht U = 2L1, der dafür verantwortlich ist, warum einige Lehrbücher diese Voraussetzung im Definieren von B-Bäumen auferlegen.

Auswischen

Es gibt zwei populäre Strategien für das Auswischen von einem B-Baum.

1. Machen Sie ausfindig und löschen Sie den Artikel, dann strukturieren Sie den Baum um, um seinen invariants ODER wiederzugewinnen
2. Tun Sie einen einzelnen Pass unten der Baum, aber vor dem Eingehen (in Besuch) eines Knotens, strukturieren Sie den Baum um, so dass sobald auf den Schlüssel, gelöscht zu werden, gestoßen wird, kann es gelöscht werden, ohne das Bedürfnis nach dem weiteren Umstrukturieren auszulösen

Der Algorithmus verwendet unten die ehemalige Strategie.

Es gibt zwei spezielle Fälle, um in Betracht zu ziehen, wenn es ein Element löscht:

1. Das Element in einem inneren Knoten ist ein Separator für seine Kinderknoten
2. Das Löschen eines Elements kann seinen Knoten unter der minimalen Zahl der Elemente und den Kindern stellen

Die Verfahren für diese Fälle sind in der Ordnung unten.

Auswischen von einem Blatt-Knoten

1. Suchen Sie nach dem Wert, um zu löschen
2. Wenn der Wert in einem Blatt-Knoten, es einfach vom Knoten löschen Sie
3. Wenn Unterlauf geschieht, überprüfen Sie Geschwister, und entweder übertragen Sie einen Schlüssel oder verschmelzen Sie die Geschwister zusammen
4. Wenn vom richtigen Kind zufällig Auswischen, den max Wert des linken Kindes wiederbekommen Sie, wenn es keinen Unterlauf hat
5. In umgekehrt der Situation, bekommen Sie das Minute-Element vom Recht wieder

Auswischen von einem inneren Knoten

Jedes Element in einem inneren Knoten handelt als ein Trennungswert für zwei Subbäume, und wenn solch ein Element gelöscht wird, entstehen zwei Fälle.

Im ersten Fall haben beide der zwei Kinderknoten nach links und des Rechts auf das gelöschte Element die minimale Zahl der Elemente, nämlich L1. Sie können dann in einen einzelnen Knoten mit 2L2 Elemente, eine Zahl angeschlossen werden, die U1 nicht überschreitet und so ein gesetzlicher Knoten ist. Wenn es nicht bekannt ist, dass dieser besondere B-Baum Doppeldaten nicht enthält, müssen wir dann auch das fragliche Element vom neuen Knoten (rekursiv) löschen.

Im zweiten Fall enthält einer der zwei Kinderknoten mehr als die minimale Zahl der Elemente. Dann muss ein neuer Separator für jene Subbäume gefunden werden. Bemerken Sie, dass das größte Element im linken Subbaum noch weniger ist als der Separator. Ebenfalls ist das kleinste Element im richtigen Subbaum das kleinste Element, das noch größer ist als der Separator. Beide jener Elemente sind in Blatt-Knoten, und irgendein kann der neue Separator für die zwei Subbäume sein.

1. Wenn der Wert in einem inneren Knoten ist, wählen Sie einen neuen Separator (entweder das größte Element im linken Subbaum oder das kleinste Element im richtigen Subbaum), entfernen Sie ihn vom Blatt-Knoten, in dem es ist, und ersetzen Sie das Element, das mit dem neuen Separator zu löschen

ist

1. Das hat ein Element von einem Blatt-Knoten gelöscht, und ist jetzt so zum vorherigen Fall gleichwertig

Das Wiederausgleichen nach dem Auswischen

Wenn das Löschen eines Elements von einem Blatt-Knoten es unter der minimalen Größe gebracht hat, müssen einige Elemente neu verteilt werden, um allen Knoten bis zum Minimum zu bringen. In einigen Fällen wird die Neuordnung den Mangel dem Elternteil bewegen, und die Neuverteilung muss wiederholend der Baum vielleicht sogar zur Wurzel angewandt werden. Da sich die minimale Element-Zählung für die Wurzel nicht wendet, ist das Machen der Wurzel, der einzige unzulängliche Knoten sein, nicht ein Problem. Der Algorithmus, um den Baum wiederzuerwägen, ist wie folgt:

1. Wenn die richtigen Geschwister mehr haben als die minimale Zahl der Elemente
2. Fügen Sie den Separator zum Ende des unzulänglichen Knotens hinzu
3. Ersetzen Sie den Separator im Elternteil mit dem ersten Element der richtigen Geschwister
4. Hängen Sie das erste Kind der richtigen Geschwister als das letzte Kind des unzulänglichen Knotens an
5. Sonst, wenn die linken Geschwister mehr haben als die minimale Zahl der Elemente
6. Fügen Sie den Separator zum Anfang des unzulänglichen Knotens hinzu
7. Ersetzen Sie den Separator im Elternteil mit dem letzten Element der linken Geschwister
8. Fügen Sie das letzte Kind der linken Geschwister als das erste Kind des unzulänglichen Knotens ein
9. Wenn beide unmittelbaren Geschwister nur die minimale Zahl der Elemente haben
10. Schaffen Sie einen neuen Knoten mit allen Elementen vom unzulänglichen Knoten, allen Elementen von einem seiner Geschwister und dem Separator im Elternteil zwischen den zwei vereinigten Geschwister-Knoten
11. Entfernen Sie den Separator vom Elternteil, und ersetzen Sie die zwei Kinder, die er mit dem vereinigten Knoten getrennt

hat

1. Wenn das die Zahl der Elemente im Elternteil unter dem Minimum bringt, wiederholen Sie diese Schritte mit diesem unzulänglichen Knoten, wenn es die Wurzel nicht ist, da die Wurzel erlaubt wird, unzulänglicher zu sein

Der einzige weitere Fall, um dafür verantwortlich zu sein, ist, wenn die Wurzel keine Elemente und ein Kind hat. In diesem Fall ist es genügend, es durch sein einziges Kind zu ersetzen.

Anfänglicher Aufbau

In Anwendungen ist es oft nützlich, einen B-Baum zu bauen, um eine große vorhandene Datenerfassung zu vertreten und dann es zusätzlich das Verwenden von StandardB-Baumoperationen zu aktualisieren. In diesem Fall soll die effizienteste Weise, den anfänglichen B-Baum zu bauen, nicht jedes Element in die anfängliche Sammlung nacheinander einfügen, aber stattdessen den anfänglichen Satz von Blatt-Knoten direkt vom Eingang zu bauen, dann die inneren Knoten von diesen bauen. Diese Annäherung an den B-Baumaufbau wird bulkloading genannt. Am Anfang hat jedes Blatt, aber das letzte ein Extraelement, das verwendet wird, um die inneren Knoten zu bauen.

Zum Beispiel, wenn die Blatt-Knoten maximale Größe 4 haben und die anfängliche Sammlung die ganzen Zahlen 1 bis 24 ist, würden wir 4 Blatt-Knoten am Anfang bauen, die 5 Werte jeder und 1 enthalten, der 4 Werte enthält:

||

||||||| }\

Wir bauen das folgende Niveau von den Blättern auf, indem wir das letzte Element von jedem Blatt-Knoten außer dem letzten nehmen. Wieder wird jeder Knoten außer dem letzten einen Extrawert enthalten. Im Beispiel, nehmen Sie an, dass die inneren Knoten höchstens 2 Werte (3 Kinderzeigestöcke) enthalten. Dann gleichen die folgenden innerer Knoten nach oben hin an würde sein:

||| }\||||||||| }\

Dieser Prozess wird fortgesetzt, bis wir ein Niveau mit nur einem Knoten erreichen und es nicht überfüllt wird. Im Beispiel bleibt nur das Wurzelniveau:

||| }\||||||||| }\

In filesystems

Zusätzlich zu seinem Gebrauch in Datenbanken wird der B-Baum auch in filesystems verwendet, um schnellen zufälligen Zugang zu einem willkürlichen Block in einer besonderen Datei zu erlauben. Das grundlegende Problem verwandelt die Dateiblock-Adresse in einen Plattenblock (oder vielleicht zu einem Zylinderkopf-Sektor) Adresse.

Einige Betriebssysteme verlangen, dass der Benutzer die maximale Größe der Datei zuteilt, wenn die Datei geschaffen wird. Die Datei kann dann zugeteilt werden, weil aneinander grenzende Platte blockiert. Das Umwandeln zu einem Plattenblock: Das Betriebssystem fügt gerade hinzu, dass der Dateiblock an den Startplattenblock der Datei richtet. Das Schema ist einfach, aber die Datei kann seine geschaffene Größe nicht überschreiten.

Andere Betriebssysteme erlauben einer Datei zu wachsen. Die resultierenden Plattenblöcke können nicht aneinander grenzend sein, so kartografisch darstellende logische Blöcke zu physischen Blöcken wird mehr beteiligt.

MS-DOS hat zum Beispiel einfachen File Allocation Table (FAT) verwendet. Das FETT hat einen Zugang für jeden Plattenblock, und dieser Zugang identifiziert sich, ob sein Block durch eine Datei verwendet wird und wenn so, die blockieren (wenn irgendwelcher) ist der folgende Plattenblock derselben Datei. Also, die Zuteilung jeder Datei wird als eine verbundene Liste im Tisch vertreten. Um die Plattenadresse des Dateiblocks zu finden, muss das Betriebssystem (oder Plattendienstprogramm) der verbundenen Liste der Datei im FETT folgend folgen. Schlechter, um einen freien Plattenblock zu finden, muss es das FETT folgend scannen. Für das MS-DOS, das nicht eine riesige Strafe war, weil die Platten und Dateien klein waren und hatte das FETT wenige Einträge und relativ kurze Dateiketten. Im FAT12 filesystem (verwendet auf Disketten und frühen Festplatten) gab es nicht mehr als 4,080 Einträge, und das FETT würde gewöhnlich im Gedächtnis ortsansässig sein. Da Platten größer geworden sind, hat die FETTE Architektur begonnen, Strafen gegenüberzustehen. Auf einer großen Platte mit FETT kann es notwendig sein zu leisten Platte liest, um die Plattenposition eines Dateiblocks zu erfahren, der zu lesen oder zu schreiben ist.

SPITZEN 20 (und vielleicht TENEX) sind 0 an 2 Niveau-Baum verwendet, der Ähnlichkeiten zu einem B-Baum hat. Ein Plattenblock war 512 36-Bit-Wörter. Wenn die Datei 512 (2) Wortblock einfügt, dann würde das Dateiverzeichnis zu diesem physischen Plattenblock hinweisen. Wenn die Datei 2 Wörter einfügt, dann würde das Verzeichnis zu einem aux Index hinweisen; die 512 Wörter dieses Index würden entweder UNGÜLTIG sein (der Block wird nicht zugeteilt), oder der Punkt zur physischen Adresse des Blocks. Wenn die Datei 2 Wörter einfügt, dann würde das Verzeichnis zu einem Block hinweisen, der einen aux-aux Index hält; jeder Zugang würde entweder UNGÜLTIG sein oder zu einem aux Index hinweisen. Folglich konnte der physische Plattenblock für eine 2 Wortdatei in zwei Platte gelegen werden liest, und lesen Sie auf dem dritten.

Die filesystem des Apfels HFS +, der NTFS des Microsofts und ein Linux filesystems, wie btrfs und Ext4, verwenden B-Bäume.

B*-trees werden im HFS und den Reiser4 Dateisystemen verwendet.

Schwankungen

Zugriffsparallelität

Lehman und Yao haben gezeigt, dass alle gelesenen Schlösser (und so gleichzeitiger Zugang außerordentlich verbessert) durch die Verbindung der Baumblöcke an jedem Niveau zusammen mit einem "folgenden" Zeigestock vermieden werden konnten. Das läuft auf eine Baumstruktur hinaus, wo sowohl Einfügung als auch Suchaktionen von der Wurzel bis das Blatt hinuntersteigen. Schreibsperren sind nur erforderlich, weil ein Baumblock modifiziert wird. Das maximiert Zugriffsparallelität durch vielfache Benutzer, eine wichtige Rücksicht für Datenbanken und/oder anderen B-Baum hat ISAM Lagerungsmethoden gestützt. Die mit dieser Verbesserung vereinigten Kosten sind, dass leere Seiten vom btree während normaler Operationen nicht entfernt werden können. (Sieh jedoch für verschiedene Strategien, das Knotenmischen und den Quellcode daran durchzuführen.)

Offene USA-5283894, gewährt 1994, scheinen, eine Weise zu zeigen, eine 'Zugriffsmöglichkeit von Meta' zu verwenden, um gleichzeitigen B+Tree Zugang und Modifizierung ohne Schlösser zu erlauben. Die Technik greift auf den Baum 'aufwärts' sowohl für Suchen als auch für Aktualisierungen mittels zusätzlicher Indizes im Gedächtnis zu, die auf die Blöcke in jedem Niveau im geheimen Block-Lager hinweisen. Keine Reorganisation dafür löscht ist erforderlich, und es gibt keine 'folgenden' Zeigestöcke in jedem Block als in Lehman und Yao.

Siehe auch

• B + Baum
• Binärer Suchbaum
• R-Baum

Referenzen

.

• . Kapitel 18: B-Bäume.
• . Abschnitt 6.2.4: Mehrwegige Bäume, Seiten 481-491. Außerdem besprechen Seiten 476-477 des Abschnitts 6.2.3 (Erwogene Bäume) 2-3 Bäume.

.

Ursprüngliche Papiere

.

• . Am 11-12 November 1971.

Links

• B-Baumzeichentrickfilm applet durch slady
• B-Baum und UB-Baum auf dem Scholarpedia Museumsdirektoren: Dr Rudolf Bayer
• B-Bäume: Erwogene Baumdatenstrukturen
• Das Wörterbuch von NIST von Algorithmen und Datenstrukturen: B-Baum
• B-Baumtutorenkurs
• InfinityDB BTree Durchführung
• Geheimes Lager vergesslicher B (+) - Bäume
• Wörterbuch des Algorithmus- und Datenstruktur-Zugangs für B*-tree