Inhalt

• Vergleichstabelle
• Definition von B-Baum
• Eigenschaften des B-Baums der Ordnung M
• Definition von Binärer Baum
• Traversal-Techniken
• Fazit

B-Tree und Binary Tree sind die Typen nichtlinearer Datenstrukturen. Die Begriffe scheinen zwar ähnlich zu sein, unterscheiden sich aber in allen Aspekten. Ein Binärbaum wird verwendet, wenn die Datensätze oder Daten im RAM statt auf der Festplatte gespeichert werden, da die Zugriffsgeschwindigkeit des RAM viel höher ist als die der Festplatte. Auf der anderen Seite wird der B-Baum verwendet, wenn die Daten auf der Festplatte gespeichert werden. Er verkürzt die Zugriffszeit, indem die Höhe des Baums verringert und die Verzweigungen im Knoten vergrößert werden.

Ein weiterer Unterschied zwischen dem B-Baum und dem Binärbaum besteht darin, dass für den B-Baum alle untergeordneten Knoten auf derselben Ebene liegen müssen, während für den Binärbaum keine solche Einschränkung besteht. Ein binärer Baum kann maximal 2 Teilbäume oder Knoten haben, wohingegen in B-Baum M keine Teilbäume oder Knoten haben kann, wobei M die Ordnung des B-Baums ist.

1. Vergleichstabelle
2. Definition
3. Hauptunterschiede
4. Fazit

Vergleichstabelle

Vergleichsbasis	B-Baum	Binärer Baum
Wesentliche Einschränkung	Ein Knoten kann maximal M untergeordnete Knoten haben (wobei M die Ordnung des Baums ist).	Ein Knoten kann maximal 2 Teilbäume haben.
Benutzt	Es wird verwendet, wenn Daten auf der Festplatte gespeichert werden.	Es wird verwendet, wenn Datensätze und Daten im RAM gespeichert werden.
Höhe des Baumes	LogM N (wobei m die Ordnung des M-Weg-Baums ist)	Log2 N
Anwendung	Datenstruktur der Code-Indizierung in vielen DBMS.	Codeoptimierung, Huffman-Codierung usw.

Definition von B-Baum

Ein B-Baum ist der ausgeglichene M-Weg-Baum und wird auch als ausgeglichener Sortierbaum bezeichnet. Es ähnelt dem binären Suchbaum, bei dem die Knoten auf der Grundlage der Inorder Traversal-Funktion organisiert sind. Die Raumkomplexität des B-Baums ist O (n). Die Komplexität der Einfüge- und Löschzeit beträgt O (log n).

Es gibt bestimmte Bedingungen, die für einen B-Baum erfüllt sein müssen:

• Die Höhe des Baumes muss so gering wie möglich sein.
• Über den Blättern des Baumes sollten sich keine leeren Teilbäume befinden.
• Die Blätter des Baumes müssen auf gleicher Höhe stehen.
• Alle Knoten sollten die geringste Anzahl von untergeordneten Knoten haben, mit Ausnahme von Leave-Knoten.

Eigenschaften des B-Baums der Ordnung M

• Jeder Knoten kann eine maximale Anzahl von M Kindern und eine minimale Anzahl von M / 2 Kindern oder eine beliebige Anzahl von 2 bis maximal haben.
• Jeder Knoten hat einen Schlüssel weniger als Kinder mit maximal M-1 Schlüsseln.
• Die Anordnung der Schlüssel erfolgt in einer bestimmten Reihenfolge innerhalb der Knoten. Alle Schlüssel im Teilbaum links vom Schlüssel sind Vorgänger des Schlüssels, und die Schlüssel rechts vom Schlüssel werden als Nachfolger bezeichnet.
• Zum Zeitpunkt des Einfügens eines vollständigen Knotens wird der Baum in zwei Teile geteilt, und der Schlüssel mit dem Medianwert wird am übergeordneten Knoten eingefügt.
• Der Zusammenführungsvorgang findet statt, wenn die Knoten gelöscht werden.

Definition von Binärer Baum

Ein binärer Baum ist eine Baumstruktur, die höchstens zwei Zeiger für ihre untergeordneten Knoten haben kann. Dies bedeutet, dass der höchste Grad, den ein Knoten haben kann, 2 ist und dass es auch Knoten mit null oder einem Grad geben kann.

Es gibt bestimmte Varianten eines Binärbaums, z. B. einen streng binären Baum, einen vollständigen binären Baum, einen erweiterten binären Baum usw.

• Der streng binäre Baum ist ein Baum, in dem jeder nicht-terminale Knoten einen linken Teilbaum und einen rechten Teilbaum haben muss.
• Ein Baum wird als vollständiger Binärbaum bezeichnet, wenn er die Bedingung 2 erfüllt ^ich Knoten auf jeder Ebene, wo i die Ebene ist.
• Threaded Binary ist ein Binärbaum, der entweder aus 0 Knoten oder 2 Knoten besteht.

Traversal-Techniken

Das Durchlaufen von Bäumen ist eine der häufigsten Operationen, die an Baumdatenstrukturen durchgeführt werden, bei denen jeder Knoten systematisch genau einmal besucht wurde.

• Inorder- In diesem Tree Traversal wird der linke Teilbaum rekursiv besucht, dann der Wurzelknoten und im letzten rechten Teilbaum.
• Preorer- In diesem Tree Traversal wird zuerst der Wurzelknoten aufgesucht, dann der linke Teilbaum und zuletzt der rechte Teilbaum.
• Postorder- Diese Technik besucht den linken Teilbaum, dann den rechten Teilbaum und zuletzt den Wurzelknoten.

1. In B-Tree ist die maximale Anzahl von Kindknoten, die ein nicht-terminaler Knoten haben kann, M, wobei M die Reihenfolge des B-Tree ist. Andererseits kann ein Binärbaum höchstens zwei Unterbäume oder untergeordnete Knoten haben.
2. B-Tree wird verwendet, wenn Daten auf der Festplatte gespeichert werden, während Binärbaum verwendet wird, wenn Daten im schnellen Speicher wie RAM gespeichert werden.
3. Ein weiteres Anwendungsgebiet für B-Tree ist die Datenstruktur der Code-Indizierung in DBMS. Im Gegensatz dazu wird Binary Tree bei der Code-Optimierung, der Huffman-Codierung usw. eingesetzt.
4. Die maximale Höhe eines B-Baums ist log_MN (M ist die Ordnung des Baumes). Im Gegensatz dazu ist die maximale Höhe des Binärbaums log₂N (N ist die Anzahl der Knoten und Basis ist 2, weil es für binär ist).

Fazit

Der B-Baum wird über Binär- und Binärsuchbaum verwendet. Der Hauptgrund dafür ist die Speicherhierarchie, bei der die CPU mit den Kanälen mit hoher Bandbreite an den Cache angeschlossen ist, während die CPU über einen Kanal mit niedriger Bandbreite an die Festplatte angeschlossen ist. Ein Binärbaum wird verwendet, wenn Datensätze im RAM gespeichert werden (klein und schnell), und ein B-Baum wird verwendet, wenn Datensätze auf der Festplatte gespeichert werden (groß und langsam). Die Verwendung eines B-Baums anstelle eines binären Baums reduziert die Zugriffszeit aufgrund des hohen Verzweigungsfaktors und der verringerten Höhe des Baums erheblich.