Was sind die Unterschiede zwischen B-Bäumen und B + -Bäumen?

293

In einem B-Baum können Sie sowohl Schlüssel als auch Daten in den internen und Blattknoten speichern , in einem B + -Baum müssen Sie die Daten jedoch nur in den Blattknoten speichern .

Gibt es einen Vorteil, wenn Sie dies in einem b + -Baum tun?

Warum nicht überall B-Bäume anstelle von B + -Bäumen verwenden, da sie intuitiv viel schneller erscheinen?

Ich meine, warum müssen Sie den Schlüssel (Daten) in einem b + -Baum replizieren?

simplfuzz
quelle
37
Ich denke, was sie sagen, ist "B-Tree" gegen B + -Tree. Sie bedeuten einen Bindestrich, kein Minuszeichen.
stu

Antworten:

421

Das Bild unten zeigt die Unterschiede zwischen B + -Bäumen und B-Bäumen.

Vorteile von B + Bäumen:

  • Da B + -Bäume keine Daten mit inneren Knoten verknüpft haben, können mehr Schlüssel auf eine Speicherseite passen. Daher sind weniger Cache-Fehler erforderlich, um auf Daten zuzugreifen, die sich auf einem Blattknoten befinden.
  • Die Blattknoten von B + -Bäumen sind verknüpft, sodass für einen vollständigen Scan aller Objekte in einem Baum nur ein linearer Durchgang durch alle Blattknoten erforderlich ist. Ein AB-Baum würde andererseits eine Durchquerung jeder Ebene im Baum erfordern. Diese Vollbaum-Durchquerung wird wahrscheinlich mehr Cache-Fehler beinhalten als die lineare Durchquerung von B + -Blättern.

Vorteil von B-Bäumen:

  • Da B-Bäume mit jedem Schlüssel Daten enthalten, können Knoten, auf die häufig zugegriffen wird, näher an der Wurzel liegen und daher schneller aufgerufen werden.

B und B + Baum

Rose Perrone
quelle
2
Ist die Anzahl der Einträge im Blattknoten eingeschränkt?
TLE
38
@TLE Gute Frage! Ja. Eine Festplatte greift gleichzeitig auf mindestens eine Speicherseite zu, daher möchten wir alle Zeiger auf einer einzelnen Speicherseite platzieren. Wir möchten nur einen Festplattenlesevorgang pro Blattzugriff benötigen, daher möchten wir einem Blatt nicht mehr als eine Seitengröße von Zeigern zuweisen. Wenn wir ein Blatt mit einer Seitengröße von Zeigern füllen und dann diesem Blatt einen weiteren Zeiger hinzufügen möchten, erstellen wir zwei untergeordnete Elemente dieses Knotens und geben jedem neuen untergeordneten Element die Hälfte der Zeiger des Blattes. Natürlich kann es zu einer Umbesetzung kommen, um sicherzustellen, dass die Höhe des Baumes auf ein Minimum beschränkt bleibt. Hilft das?
Rose Perrone
Der letzte Zeiger jedes Blattknotens des B-Baums sollte auf den nächsten Blattknoten zeigen, oder?
Camino
8
Es tut mir leid, dass ich so einen alten Thread gestoßen habe, aber der Kommentar von @ Babyburger, wie der Kommentar von camino richtig war, ist nicht wirklich wahr. Ein B-Baum hat tatsächlich keine verbundenen Blattknoten. Ein B +, klar.
Jason
Vielen Dank für die hervorragende Antwort. Was ist ein Anwendungsfall, wenn ein vollständiger Scan der Objekte in einem B / B + -Baum in einem Datenbankkontext erforderlich wäre? Da es hauptsächlich für die Indizierung verwendet wird, müssten Suchvorgänge kaum jemals den gesamten Baum nach rechts scannen und stattdessen über den Indexpfad durchlaufen. Ist das richtig?
Siddhartha
113

Der Hauptvorteil von B + -Bäumen gegenüber B-Bäumen besteht darin, dass Sie mehr Zeiger auf andere Knoten einpacken können, indem Sie Zeiger auf Daten entfernen, wodurch das Fanout erhöht und möglicherweise die Tiefe des Baums verringert wird.

Der Nachteil ist, dass es keine frühen Outs gibt, wenn Sie möglicherweise eine Übereinstimmung in einem internen Knoten gefunden haben. Da beide Datenstrukturen große Fanouts aufweisen, wird die überwiegende Mehrheit Ihrer Übereinstimmungen ohnehin auf Blattknoten stattfinden, wodurch der B + -Baum im Durchschnitt effizienter wird.

Vic E.
quelle
1
Ich bevorzuge Jeffs Antwort, weil sie den Unterschied in der Effizienz bei einem vollständigen Scan hervorhebt.
Rose Perrone
Ich bin wirklich verwirrt, weil das Durchlaufen eines B-Baums mit einer Durchquerung in der richtigen Reihenfolge alle Werte in sortierter Reihenfolge in O (n) -Zeit liest. Wenn jeder Baumknoten für die physische Seitengröße optimal dimensioniert ist, scheinen die Dinge nicht optimaler zu werden. Umgekehrt betragen die Kosten, um zum ersten (kleinsten) Wert in einem b + -Baum zu gelangen, O (log n) und dann, um durch jedes Blatt zu gehen, O (n), sodass die Gesamtkosten O (log n + n) sind. Dies ist mehr Arbeit und mehr Festplattenlesevorgänge, was sinnvoll ist, da der Baum all diese zusätzlichen Daten enthält. Ich verstehe es nicht
Eric
Was wäre ein anderes Wort für "Fanout" im obigen Satz?
Jorge Bucaran
3
@JorgeBucaran Fanout = Anzahl der Kanten, die aus einem Knoten kommen
Bantmen
33

B + Bäume sind viel einfacher und leistungsfähiger, um einen vollständigen Scan durchzuführen, wie bei jedem Datenelement, das der Baum indiziert, da die Endknoten eine verknüpfte Liste bilden. Um einen vollständigen Scan mit einem B-Baum durchzuführen, müssen Sie einen vollständigen Baumdurchlauf durchführen, um alle Daten zu finden.

B-Bäume hingegen können schneller sein, wenn Sie eine Suche durchführen (indem Sie nach einem bestimmten Datenelement nach Schlüssel suchen), insbesondere wenn sich der Baum im RAM oder einem anderen Nicht-Block-Speicher befindet. Da Sie häufig verwendete Knoten in der Baumstruktur erhöhen können, sind weniger Vergleiche erforderlich, um zu den Daten zu gelangen.

Jeff Mc
quelle
1
Würden Sie zustimmen, würde ein B + -Baum für Situationen verwendet, in denen möglicherweise alle Daten sequentiell gelesen werden und somit über die Blätter gehen können. Während der B-Baum ideal für Situationen mit wahlfreiem Zugriff wäre?
JDPeckham
31
  1. In einem B-Baum werden Suchschlüssel und Daten in internen oder Blattknoten gespeichert. In einem B + -Baum werden Daten jedoch nur in Blattknoten gespeichert.
  2. Der vollständige Scan eines B + -Baums ist sehr einfach, da alle Daten in Blattknoten gefunden werden. Ein vollständiger Scan eines B-Baums erfordert eine vollständige Durchquerung.
  3. In einem B-Baum können Daten in Blattknoten oder internen Knoten gefunden werden. Das Löschen interner Knoten ist sehr kompliziert. In einem B + -Baum werden Daten nur in Blattknoten gefunden. Das Löschen von Blattknoten ist einfach.
  4. Das Einfügen in den B-Baum ist komplizierter als das Einfügen in den B + -Baum.
  5. B + -Bäume speichern redundante Suchschlüssel, aber B-Baum hat keinen redundanten Wert.
  6. In einem B + -Baum werden Blattknotendaten als sequentielle verknüpfte Liste sortiert, in einem B-Baum kann der Blattknoten jedoch nicht mithilfe einer verknüpften Liste gespeichert werden. Die Implementierungen vieler Datenbanksysteme bevorzugen die strukturelle Einfachheit eines B + -Baums.
androidcodehunter
quelle
15

Beispiel aus Datenbanksystemkonzepten 5 ..

B + -Baum B + Baum

entsprechender B-Baum Btree

Camino
quelle
5
Ich glaube nicht, dass ein B-Baum Links zu den Kindern des Knotens hat. Zum Beispiel bilden die Clearview bucketzum Mianus Bucket. Es würde sowieso nicht viel Sinn machen, dies zu tun, da zwischen den beiden Downtown bucketdie Menge gesucht werden muss, wenn Sie einen Index-Scan in einem B-Baum durchführen möchten (erfordert Backtracking). Woher hast du das?
Evan Carroll
1
@EvanCarroll Datenbanksystemkonzepte 5., vielleicht müssen Sie mit dem Autor bestätigen :)
Camino
11

Definieren Sie "viel schneller". Asymptotisch sind sie ungefähr gleich. Die Unterschiede liegen darin, wie sie den Sekundärspeicher nutzen. Die Wikipedia-Artikel zu B-Bäumen und B + -Bäumen sehen ziemlich vertrauenswürdig aus.

Charlie Martin
quelle
2
Ich stimme Charlie zu. Da ein Knoten eines B-Baums eine sekundäre Speicherseite oder einen sekundären Block darstellt, erfordert der Übergang von einem Knoten zu einem anderen einen zeitaufwändigen Seitenwechsel.
11

Adegoke A, Amit

Ich denke, ein entscheidender Punkt, den Sie vermissen, ist der Unterschied zwischen Daten und Zeigern, wie in diesem Abschnitt erläutert.

Zeiger: Zeiger auf andere Knoten.

Daten: - Im Kontext von Datenbankindizes sind Daten nur ein weiterer Zeiger auf reale Daten (Zeilen), die sich an einer anderen Stelle befinden.

Daher hat im Fall eines B-Baums jeder Knoten drei Informationsschlüssel, Zeiger auf Daten, die den Schlüsseln zugeordnet sind, und Zeiger auf untergeordnete Knoten.

Im internen B + -Baum behalten Schlüssel und Zeiger den untergeordneten Knoten, während der Blattknoten Schlüssel und Zeiger auf zugehörige Daten behält. Dies ermöglicht eine größere Anzahl von Schlüsseln für eine bestimmte Knotengröße. Die Größe des Knotens wird hauptsächlich durch die Blockgröße bestimmt.

Der Vorteil, mehr Schlüssel pro Knoten zu haben, wurde oben ausführlich erläutert, damit ich meinen Tippaufwand sparen kann.

Saket
quelle
10

B + Bäume eignen sich besonders gut für blockbasierten Speicher (z. B. Festplatte). In diesem Sinne erhalten Sie zum Beispiel mehrere Vorteile (von oben):

  • Hoher Fanout / geringe Tiefe: Das bedeutet, dass Sie weniger Blöcke benötigen, um an die Daten zu gelangen. Wenn Daten mit den Zeigern vermischt sind, erhält jeder Lesevorgang weniger Zeiger, sodass Sie mehr Suchvorgänge benötigen, um an die Daten zu gelangen

  • Einfache und konsistente Blockspeicherung: Ein innerer Knoten hat N Zeiger, sonst nichts, ein Blattknoten hat Daten, sonst nichts. das macht es einfach zu analysieren, zu debuggen und sogar zu rekonstruieren.

  • Eine hohe Schlüsseldichte bedeutet, dass sich die obersten Knoten mit ziemlicher Sicherheit im Cache befinden. In vielen Fällen werden alle inneren Knoten schnell zwischengespeichert, sodass nur der Datenzugriff auf die Festplatte erfolgen muss.

Javier
quelle
2
meistens für In-Memory-Bäume; Es gibt aber auch andere beliebte Optionen, wie z. B. rot-schwarze Bäume, Überspringlisten und dergleichen.
Javier
B-Bäume sind auch für eine effiziente blockbasierte Speicherung ausgelegt, wodurch die asymptotische Anzahl von Knotenzugriffen begrenzt wird. Andernfalls kann bei Verwendung eines speicherähnlichen Speichermediums mit wahlfreiem Zugriff ein selbstausgleichender Binärbaum wie ein rot-schwarzer Baum verwendet werden, um bessere Ergebnisse zu erzielen.
Dionyziz
sollte Ihr erster Punkt nicht "weniger sucht" statt "mehr sucht" sagen. Kleinere Tiefe -> weniger sucht
Jesse
1
@ Jesse: hohe Fanout => geringe Tiefe => weniger Suchvorgänge, aber das Mischen von Daten und Zeigern bedeutet weniger Zeiger => niedrige Fanout => mehr Tiefe => mehr Suchvorgänge
Javier
1
@AdegokeA: Ein B + -Baum hat zwei Arten von Knoten: innere Knoten mit nur Schlüsseln und Zeigern, keine Daten; und Blattknoten mit Daten und ohne Zeiger. Dies ermöglicht eine maximale Anzahl von Schlüsseln auf jedem inneren Knoten. Wenn Sie Daten auf einem inneren Knoten speichern, können Sie weniger Zeiger anpassen und Ihr Baum wird größer.
Javier
5

Da in B + Tree nur Zeiger in den internen Knoten gespeichert sind, wird ihre Größe erheblich kleiner als die internen Knoten von B Tree (in denen beide Daten + Schlüssel gespeichert sind). Daher können die Indizes des B + -Baums in einem einzigen gelesenen Datenträger aus dem externen Speicher abgerufen und verarbeitet werden, um den Ort des Ziels zu finden. Wenn es sich um einen B-Baum handelt, ist für jeden Entscheidungsprozess ein Festplattenlesevorgang erforderlich. Hoffe, ich habe meinen Standpunkt klargestellt! :) :)

VS7
quelle
4

** **.

Der Hauptnachteil von B-Tree ist die Schwierigkeit, die Schlüssel nacheinander zu durchlaufen. Der B + Tree behält die Schnellzugriffseigenschaft des B-Tree bei und ermöglicht gleichzeitig einen schnellen sequentiellen Zugriff

** ref: Datenstrukturen mit C // Autor: Aaro M Tenenbaum

http://books.google.co.in/books?id=X0Cd1Pr2W0gC&pg=PA456&lpg=PA456&dq=drawback+of+B-Tree+is+the+difficulty+of+Traversing+the+keys+sequential&source=bl&ots=pGcPQSEJMS& F9MY7zEXYAMVKl_Sg4W-0LTRor8 & hl = en & sa = X & ei = nD5AUbeeH4zwrQe12oCYAQ & ved = 0CDsQ6AEwAg # v = onepage & q = Nachteil% 20von% 20B-Baum% 20ist% 20% 20% 20% 20% 20% 20% 20% 20%

Kapil Kumar
quelle
1
Dies hätte die richtige Antwort sein sollen. Kurzum: Referenzort.
Theodore Zographos
2

Nehmen Sie ein Beispiel: Sie haben eine Tabelle mit riesigen Daten pro Zeile. Das bedeutet, dass jede Instanz des Objekts groß ist.

Wenn Sie hier den B-Baum verwenden, wird die meiste Zeit damit verbracht, die Seiten mit Daten zu scannen - was keinen Nutzen hat. In Datenbanken ist dies der Grund für die Verwendung von B + Trees, um das Scannen von Objektdaten zu vermeiden.

B + Bäume trennen Schlüssel von Daten.

Wenn Ihre Datengröße jedoch geringer ist, können Sie sie mit einem Schlüssel speichern, wie es der B-Baum tut.

Amit
quelle
1
"Wenn Sie hier den B-Baum verwenden, wird die meiste Zeit damit verbracht, die Seiten mit Daten zu scannen" - nicht erforderlich. B-Tree-Knoten können nur "Zeiger" auf Daten auf der Disc behalten, nicht auf Daten selbst.
TT_
2

Der Hauptunterschied zwischen B-Baum und B + -Baum besteht darin, dass der B-Baum die redundante Speicherung von Suchschlüsselwerten eliminiert. Da Suchschlüssel im B-Baum nicht wiederholt werden, können wir den Index möglicherweise nicht mit weniger Baumknoten speichern Da Suchschlüssel, die in Nicht-Blattknoten erscheinen, nirgendwo anders im B-Baum erscheinen, müssen wir für jeden Suchschlüssel in einem Nicht-Blattknoten ein zusätzliches Zeigerfeld einfügen. Dies sind Platzvorteile für den B-Baum, da keine Wiederholung auftritt und für große Indizes verwendet werden kann.

Maria
quelle
1
Interessanterweise sind die Gedanken zur Wiederholung unter den Antworten hier einzigartig und sinnvoller als das Durchlaufen eines B + -Baums in der Reihenfolge, das effizienter ist als das Durchlaufen eines B-Baums in der Reihenfolge. Soweit ich das beurteilen kann, ist das entweder nicht ganz richtig oder nicht die ganze Geschichte, da die Durchquerung eines B-Baums O (n) ist und das Finden des kleinsten Knotens in einem B + -Baum O (log n) ist und dann Das Durchqueren jedes Blattes ist zusätzlich O (n). Wenn Sie jedoch etwas mit einem kleinen Wertebereich indizieren, z. B. ein boolesches Feld, ist der b + -Baum aufgrund seiner doppelten Behandlung viel sinnvoller als ein b-Baum.
Eric
1

Ein B + -Baum ist ein ausgeglichener Baum, in dem jeder Pfad von der Wurzel des Baums zu einem Blatt gleich lang ist und jeder nichtblättrige Knoten des Baums zwischen [n / 2] und [n] Kindern hat, wobei n ist für einen bestimmten Baum behoben. Es enthält Indexseiten und Datenseiten. Binärbäume haben nur zwei Kinder pro Elternknoten, B + -Bäume können eine variable Anzahl von Kindern für jeden Elternknoten haben

Vivek Rakholiya
quelle
1
Nur aus Gründen der Klarheit sind B-Bäume keine binären Bäume. Tatsächlich sind B-Bäume und B + -Bäume in Konstruktion und Verwendung näher beieinander als Binärbäume. Die Wiki-Artikel können beim Löschen der Definitionen helfen - B + Baum , B-Baum und Binärbaum
uutsav
1

Eine mögliche Verwendung von B + -Bäumen besteht darin, dass sie für Situationen geeignet sind, in denen der Baum so groß wird, dass er nicht in den verfügbaren Speicher passt. Daher würden Sie im Allgemeinen erwarten, mehrere E / A-Vorgänge auszuführen.
Es kommt häufig vor, dass ein B + -Baum verwendet wird, auch wenn er tatsächlich in den Speicher passt, und Ihr Cache-Manager ihn dann möglicherweise dauerhaft dort aufbewahrt. Dies ist jedoch ein Sonderfall, nicht der allgemeine, und die Caching-Richtlinie unterscheidet sich von der B + -Baumpflege als solche.

Außerdem werden in einem B + -Baum die Blattseiten in einer verknüpften Liste (oder doppelt verknüpften Liste) miteinander verknüpft, wodurch das Durchlaufen (für Bereichssuchen, Sortieren usw.) optimiert wird. Die Anzahl der Zeiger ist also eine Funktion des spezifischen Algorithmus, der verwendet wird.

Stapelprogrammierer
quelle
Dies ist eine Antwort auf die Frage, warum wir nicht überall B-Bäume anstelle von B + -Bäumen verwenden sollten :)
Stapelprogrammierer
3
Aber Sie haben, soweit wir wissen, nur eine Seite beschrieben, mit Ihrer Antwort könnten B-Bäume genauso funktionieren. Das OP hat darum gebeten, die Unterschiede zu erklären, und Sie haben nur über das eine und nicht über das andere gesprochen. Sie können kein Venn-Diagramm mit einem Kreis haben!
Malfist