Hauptunterschied: In Computern sind die Binärbäume Baumdatenstrukturen, in denen die Daten gespeichert werden und die dem Benutzer den Zugriff auf die Daten zum algorithmischen Zeitpunkt ermöglichen, sie durchsuchen, einfügen und löschen können. Der Unterschied zwischen einem B- und B + -Baum besteht darin, dass in einem B-Baum die Schlüssel und Daten sowohl im internen als auch im Blattknoten gespeichert werden können, während in einem B + -Baum die Daten und Schlüssel nur in den Blattknoten gespeichert werden können .
Die binären Bäume sind ausbalancierte Suchbäume, die auf sekundären Speichermedien mit direktem Zugriff wie Magnetplatten gut funktionieren. Rudolf Bayer und Ed McCreight erfanden das Konzept eines B-Baums.
Ein B-Baum ist ein verallgemeinerter binärer Suchbaum, in dem jeder Knoten mehr als zwei Kinder haben kann. Jeder interne Knoten in einem B-Baum enthält eine Reihe von Schlüsseln. Diese Schlüssel trennen die Werte und bilden die Unterbäume. Die internen Knoten in einem B-Baum können eine variable Anzahl von Kindknoten haben, die innerhalb eines vordefinierten Bereichs angeordnet sind. Zu dem Zeitpunkt, zu dem Daten eingefügt oder aus einem jeweiligen Knoten entfernt werden, ändert sich die Anzahl der untergeordneten Knoten. Um den vordefinierten Bereich beizubehalten, können interne Knoten verbunden oder aufgeteilt werden. In einem B-Baum ist ein Bereich von untergeordneten Knoten zulässig, aufgrund dessen der vordefinierte Bereich gepflegt werden muss.
Die B-Bäume müssen im Gegensatz zu anderen selbstausgleichenden Suchbäumen nicht häufig neu ausbalanciert werden. Die Knoten in diesen Bäumen sind nicht immer voll; Daher werden die Räume in diesen Bäumen unnötig verbraucht, was zu Raumverschwendung führt. Für eine bestimmte Implementierung werden normalerweise nur die untere und obere Grenze der Anzahl der untergeordneten Knoten festgelegt. In einem 2-3-B-Baum (oft einfach als 2-3-Baum bezeichnet) kann jeder interne Knoten beispielsweise nur zwei oder drei untergeordnete Knoten haben.
Darüber hinaus ist der B-Baum für Systeme optimiert, die große Datenblöcke lesen und schreiben. Es wird häufig in Datenbanken und Dateisystemen verwendet. Im B-Baum werden alle Knoten auf den gleichen Auswuchttiefen von den Wurzelknoten gehalten. Diese Tiefen nehmen mit zunehmender Anzahl von Elementen langsam zu; Dies führt dazu, dass sich alle Blattknoten um einen weiteren Knoten von der Wurzel entfernt befinden. Darüber hinaus sind die B-Bäume im Vergleich zu anderen Implementierungen hinsichtlich des Zeitaufwands für den Zugriff auf die Daten vorteilhafter.
Ein B + -Baum ist ein n-Array-Baum mit einem Knoten, der aus einer großen Anzahl von Kindern pro Knoten besteht. Die Wurzel kann ein Blatt oder ein Knoten sein, der mehr als zwei Kinder enthält. Ein B + -Baum besteht aus einer Wurzel, internen Knoten und Blättern.
Ein B + -Baum ist das gleiche wie ein B-Baum; Der einzige Unterschied ist, dass im B + -Baum eine zusätzliche Ebene mit verknüpften Blättern hinzugefügt wird. Im Gegensatz zum B-Baum enthält jeder Knoten in einem B + -Baum nur Schlüssel und keine Schlüssel-Wert-Paare.
Darüber hinaus misst der Ausgleichsfaktor oder die Reihenfolge eines B + -Baums die Kapazität der internen Knoten in einem Baum, dh die Anzahl der Knoten, die sie haben können. Die tatsächliche Anzahl der Kinder eines Knotens ist für interne Knoten begrenzt. Die Wurzel ist jedoch eine Ausnahme, da sie mehr als zwei Kinder haben darf. Wenn die Reihenfolge eines B + -Baums beispielsweise 7 ist, kann jeder interne Knoten (außer der Wurzel) zwischen 4 und 7 Kinder haben. während der Stamm zwischen 2 und 7 haben kann. Der primäre Wert des B + -Baums besteht im Speichern von Daten zum effizienten Abrufen in einem blockorientierten Speicherkontext und insbesondere in Dateisystemen.
Der Hauptwert des B + -Baums liegt in der Speicherung und Pflege der Daten, damit die Daten nicht verloren gehen. Dieser Ansatz wird insbesondere im blockorientierten Speicherkontext und in bestimmten Dateisystemen angewendet. Die Blätter, die die untersten Indexblöcke sind, des B + -Baums sind häufig in einer verknüpften Liste miteinander verbunden. Daher werden Bereichsabfragen oder eine geordnete Wiederholung durch die Blöcke einfacher und effizienter. Außerdem wird der Raumfaktor nicht in B + -Bäumen verschwendet. Der B + -Baum bietet ein effizientes Gehäuse-Datenstrukturformat, das den Zugriff und die Speicherung vereinfacht. Die B + -Bäume sind besonders nützlich als Datenbanksystemindex, bei dem sich die Daten normalerweise auf einer Platte befinden.
Vergleich zwischen B-Baum und B + -Baum:
B Baum | B + Baum | |
Kurze Webbeschreibungen | Ein AB-Baum ist eine Organisationsstruktur zum Speichern und Abrufen von Informationen in Form eines Baums, in dem sich alle Endknoten in der gleichen Entfernung von der Basis befinden und alle Nicht-Endknoten zwischen n und 2 n Unterbäume oder Zeiger (wo) n ist eine ganze Zahl). | Der B + -Baum ist ein n-Array-Baum mit einer Variablen, aber häufig einer großen Anzahl von Kindern pro Knoten. Ein B + -Baum besteht aus einer Wurzel, internen Knoten und Blättern. Die Wurzel kann entweder ein Blatt oder ein Knoten mit zwei oder mehr Kindern sein. |
Auch bekannt als | Ausgeglichener Baum. | B plus Baum. |
Platz | Auf) | Auf) |
Suche | O (log n) | O (log b n) |
Einfügen | O (log n) | O (log b n) |
Löschen | O (log n) | O (log b n) |
Lager | In einem B-Baum werden Schlüssel und Daten gesucht, die in internen oder Blattknoten gespeichert sind. | In einem B + -Baum werden Daten nur in Blattknoten gespeichert. |
Daten | Die Blattknoten der drei Speicherzeiger zeigen auf Datensätze statt auf tatsächliche Datensätze. | Die Blattknoten des Baums speichern den tatsächlichen Datensatz und nicht Zeiger auf Datensätze. |
Platz | Diese Bäume verschwenden Platz | Dort verschwenden Bäume keinen Platz. |
Funktion der Blattknoten | Im B-Baum kann der Blattknoten nicht mithilfe der verknüpften Liste gespeichert werden. | Im B + -Baum werden Blattknotendaten in einer sequentiell verknüpften Liste geordnet. |
Suchen | Hier wird die Suche im B-Baum schwierig, da keine Daten im Blattknoten gefunden werden können. | Hier ist die Suche nach Daten in einem B + -Baum sehr einfach, da alle Daten in Blattknoten gefunden werden. |
Zugänglichkeit suchen | Hier im B-Baum ist die Suche im Vergleich zu einem B + -Baum nicht so einfach. | Hier im B + -Baum wird die Suche einfach. |
Redundanter Schlüssel | Sie speichern keinen redundanten Suchschlüssel. | Sie speichern redundanten Suchschlüssel. |
Anwendungen | Sie sind eine ältere Version und im Vergleich zu den B + -Bäumen nicht so vorteilhaft. | Viele Datenbanksystem-Implementierer bevorzugen die strukturelle Einfachheit eines B + -Baums. |
