B-Baum- und B + -Baum-Datenstruktur in C ++

b tree b tree data structure c

Dieses C ++ - Tutorial erklärt die B-Tree- und B + Tree-Datenstrukturen. Sie werden zum Speichern von Daten auf Datenträgern verwendet, wenn die gesamten Daten nicht im Hauptspeicher gespeichert werden können:

B-Tree ist ein selbstausgeglichener Baum sowie ein spezialisierter M-Way-Baum, der für den Festplattenzugriff verwendet wird.

Wenn die zu speichernde Datenmenge sehr hoch ist, können wir nicht die gesamten Daten im Hauptspeicher speichern. Daher speichern wir Daten auf der Festplatte. Der Datenzugriff von der Festplatte dauert im Vergleich zum Hauptspeicherzugriff länger.

Wenn die Anzahl der Schlüssel der auf Datenträgern gespeicherten Daten sehr hoch ist, wird normalerweise in Form von Blöcken auf die Daten zugegriffen. Die Zeit für den Zugriff auf diese Blöcke ist direkt proportional zur Höhe des Baums.

=> Klicken Sie hier für die Absolute C ++ - Schulungsserie.

Was du lernen wirst:

• B-Tree In C ++
  • Grundlegende Operationen von B-Tree
    • # 1) Suchen
    • # 2) Einfügen
    • # 3) Löschen
  • Anwendungen von B-Bäumen
• B + Tree In C ++
  • Vorteile von B + Bäumen
• Unterschied zwischen B-Tree und B + Tree
• Fazit
  • Literatur-Empfehlungen

B-Tree In C ++

Der B-Baum ist ein flacher Baum, d. H. Die Höhe des B-Baums wird auf ein Minimum beschränkt. Stattdessen werden so viele Schlüssel in jeden Knoten des B-Baums eingefügt. Indem Sie die Höhe des B-Baums auf ein Minimum beschränken, ist der Zugriff im Vergleich zu anderen ausgeglichenen Bäumen wie AVL-Bäumen schneller.

Ein typischer B-Baum ist unten dargestellt:

wie man eine Bittorrent-Datei öffnet

Im Allgemeinen wird die Knotengröße im B-Baum gleich der Blockgröße gehalten.

Nachfolgend sind einige der Eigenschaften von B-Tree aufgeführt.

• Alle Blätter des B-Baumes sind auf dem gleichen Niveau.
• Ein B-Baum der Ordnung m kann höchstens m-1 Schlüssel und m Kinder haben.
• Jeder Knoten im B-Baum hat höchstens m Kinder.
• Der Wurzelknoten muss mindestens zwei Knoten haben.
• Jeder Knoten außer dem Wurzelknoten und dem Blattknoten enthält m / 2 untergeordnete Knoten.

Als nächstes diskutieren wir einige der grundlegenden Operationen des B-Baums.

Grundlegende Operationen von B-Tree

Im Folgenden sind einige der grundlegenden Operationen von B-Tree aufgeführt.

# 1) Suchen

Die Suche im B-Baum ähnelt der in BST. Wenn wir im obigen Baum nach Punkt 3 suchen möchten, gehen wir wie folgt vor:

• Vergleiche 3 mit Wurzelelementen. Hier 3<6 and 3 <15. So we proceed to the left subtree.
• Vergleichen Sie 3 mit 4 im linken Teilbaum. Wie 3<4, we proceed to the left subtree of node 4.
• Der nächste Knoten hat zwei Schlüssel, 2 und 3. 3> 2, während 3 = 3. Wir haben also den Schlüssel an diesem Knoten gefunden. Kehren Sie zum gefundenen Ort zurück.

Die Suche im B-Baum hängt von der Höhe des Baums ab. Die Suche nach einem bestimmten Element dauert normalerweise 0 (log n).

# 2) Einfügen

Das Einfügen eines neuen Elements in den B-Baum erfolgt auf Blattknotenebene.

Es folgt die Abfolge der Schritte (Algorithmus) zum Einfügen eines neuen Elements in den B-Baum.

• Durchqueren Sie den B-Baum, um eine Stelle an den Blattknoten zu finden, an der das Element eingefügt werden soll.
• Wenn der Blattknoten Schlüssel enthält
• Andernfalls, wenn Blattknotenschlüssel = m-1, dann:
  • Fügen Sie ein neues Element in eine zunehmende Anzahl von Elementen ein.
  • Nehmen Sie den Median der Knoten und teilen Sie den Knoten in zwei Knoten auf.
  • Schieben Sie den Median auf den übergeordneten Knoten.
  • Wenn der übergeordnete Knotenschlüssel = m-1 ist, wiederholen Sie die obigen Schritte auch für den übergeordneten Knoten. Dies geschieht so lange, bis wir den entsprechenden Blattknoten gefunden haben.
• Fügen Sie zum Schluss das Element ein.

Wir haben die Insertion in den B-Baum wie folgt demonstriert.

Fügen wir Punkt 70 in den unten gezeigten Baum ein.

VPN für kodi

Der angegebene Baum hat den Mindestgrad 'm' = 3. Daher kann jeder Knoten 2 * m -1 = 5 Schlüssel darin aufnehmen.

Jetzt fügen wir Element 70 ein. Da wir 5 Schlüssel in einem Knoten haben können, vergleichen wir Element 70 mit dem Stammelement 30. Da 70> 30, fügen wir Element 70 in den rechten Teilbaum ein.

Im rechten Teilbaum haben wir einen Knoten mit den Schlüsseln 40, 50, 60. Da jeder Knoten 5 Schlüssel enthalten kann, fügen wir das Element 70 in diesen Knoten selbst ein.

Nach dem Einfügen sieht der B-Baum wie folgt aus.

# 3) Löschen

Ebenso wie das Einfügen erfolgt das Löschen des Schlüssels auch auf Blattknotenebene. Im Gegensatz zum Einfügen ist das Löschen jedoch komplizierter. Der zu löschende Schlüssel kann entweder ein Blattknoten oder ein interner Knoten sein.

Um einen Schlüssel zu löschen, folgen Sie der folgenden Abfolge von Schritten (Algorithmus).

1. Suchen Sie den Blattknoten.

2. Wenn die Anzahl der Schlüssel in einem Knoten> m / 2 ist, löschen Sie den angegebenen Schlüssel vom Knoten.

3. Wenn der Blattknoten keine m / 2 Schlüssel hat, müssen wir die Schlüssel vervollständigen, indem wir Schlüssel aus den rechten oder linken Teilbäumen nehmen, um den B-Baum zu pflegen.

Wir folgen diesen Schritten:

• Wenn der linke Teilbaum m / 2 Elemente enthält, verschieben wir sein größtes Element zum übergeordneten Knoten und verschieben das dazwischenliegende Element an die Stelle, an der der Schlüssel gelöscht wurde.
• Wenn der rechte Teilbaum m / 2 Elemente enthält, verschieben wir sein kleinstes Element zum übergeordneten Knoten und verschieben das dazwischenliegende Element an die Stelle, an der der Schlüssel gelöscht wurde.

Vier. Wenn kein Knoten m / 2 Knoten hat, können die obigen Schritte nicht ausgeführt werden. Daher erstellen wir einen neuen Blattknoten, indem wir zwei Blattknoten und das dazwischenliegende Element des übergeordneten Knotens verbinden.

5. Wenn ein Elternteil keine m / 2 Knoten hat, wiederholen wir die obigen Schritte für den betreffenden Elternknoten. Diese Schritte werden wiederholt, bis wir einen ausgeglichenen B-Baum erhalten.

Im Folgenden finden Sie eine Abbildung zum Löschen eines Knotens aus dem B-Baum.

Betrachten Sie noch einmal den folgenden B-Baum.

Was ist der beste Musik-Downloader für Android-Handy

Nehmen wir an, wir möchten den Schlüssel 60 aus dem B-Baum löschen. Wenn wir den B-Baum überprüfen, können wir feststellen, dass der zu löschende Schlüssel im Blattknoten vorhanden ist. Wir löschen den Schlüssel 60 von diesem Blattknoten.

Jetzt sieht der Baum wie folgt aus:

Wir können feststellen, dass nach dem Löschen des Schlüssels 60 der B-Baum-Blattknoten die erforderlichen Eigenschaften erfüllt und wir keine weiteren Änderungen am B-Baum vornehmen müssen.

Wenn wir jedoch Schlüssel 20 löschen müssten, wäre nur Schlüssel 10 im linken Blattknoten geblieben. In diesem Fall müssten wir die Wurzel 30 zum Blattknoten verschieben und den Schlüssel 40 zur Wurzel bewegen.

Daher sollte beim Löschen eines Schlüssels aus dem B-Baum Vorsicht geboten sein und die Eigenschaften des B-Baums sollten nicht verletzt werden.

Durchquerung im B-Baum

Die Durchquerung im B-Baum ähnelt auch der Inorder-Durchquerung in BST. Wir beginnen rekursiv von links, kommen dann zur Wurzel und gehen zum linken Teilbaum.

Anwendungen von B-Bäumen

• B-Bäume werden zum Indizieren der Daten verwendet, insbesondere in großen Datenbanken, da der Zugriff auf Daten, die in großen Datenbanken auf Datenträgern gespeichert sind, sehr zeitaufwändig ist.
• Das Durchsuchen von Daten in größeren unsortierten Datensätzen nimmt viel Zeit in Anspruch, kann jedoch durch Indizieren mit dem B-Baum erheblich verbessert werden.

B + Tree In C ++

B + -Baum ist eine Erweiterung des B-Baums. Der Unterschied zwischen B + -Baum und B-Baum besteht darin, dass in B + -Baum die Schlüssel und Datensätze sowohl als interne als auch als Blattknoten gespeichert werden können, während in B + -Bäumen die Datensätze als Blattknoten und die Schlüssel nur in internen Knoten gespeichert werden.

Die Datensätze sind in einer verknüpften Liste miteinander verknüpft. Diese Anordnung macht die Suche nach B + -Bäumen schneller und effizienter. Interne Knoten des B + -Baums werden als Indexknoten bezeichnet.

Die B + -Bäume haben zwei Ordnungen, d. H. Eine für interne Knoten und eine für Blatt- oder externe Knoten.

Ein Beispiel für einen B + -Baum ist unten dargestellt.

Da B + Tree eine Erweiterung von B-Tree ist, gelten die grundlegenden Operationen, die wir unter dem Thema B-Tree besprochen haben, weiterhin.

Beim Einfügen und Löschen sollten die grundlegenden Eigenschaften von B + Trees erhalten bleiben. Der Löschvorgang im B + -Baum ist jedoch vergleichsweise einfacher, da die Daten nur in den Blattknoten gespeichert werden und immer aus den Blattknoten gelöscht werden.

Vorteile von B + Bäumen

• Wir können Datensätze in einer gleichen Anzahl von Festplattenzugriffen abrufen.
• Im Vergleich zum B-Baum ist die Höhe des B + -Baums geringer und bleibt ausgeglichen.
• Wir verwenden Schlüssel zur Indizierung.
• Auf Daten im B + -Baum kann nacheinander oder direkt zugegriffen werden, wenn die Blattknoten in einer verknüpften Liste angeordnet sind.
• Die Suche ist schneller, da Daten nur in Blattknoten und als verknüpfte Liste gespeichert werden.

Unterschied zwischen B-Tree und B + Tree

Fazit

In diesem Tutorial haben wir B-Tree und B + Tree ausführlich besprochen. Diese beiden Datenstrukturen werden verwendet, wenn eine sehr hohe Datenmenge vorhanden ist und nicht alle Daten im Hauptspeicher gespeichert werden können. Um Daten auf Datenträgern zu speichern, verwenden wir B-Tree und B + Tree.

Die B-Baum-Suche ist etwas langsamer, da die Daten sowohl in internen als auch in Blattknoten gespeichert werden. B + Baum ist eine Erweiterung von B-Baum und die Daten hier werden nur in Blattknoten gespeichert. Aufgrund dieses Faktors ist die Suche in einem B + -Baum schneller und effizienter.

=> Besuchen Sie hier für die vollständige Liste der C ++ - Tutorials.

Literatur-Empfehlungen

• AVL-Baum- und Heap-Datenstruktur in C ++
• Datenstruktur der verknüpften Liste in C ++ mit Abbildung
• Warteschlangendatenstruktur in C ++ mit Illustration
• Stapeldatenstruktur in C ++ mit Illustration
• Datenstruktur für zirkuläre verknüpfte Listen in C ++ mit Abbildung
• Einführung in Datenstrukturen in C ++
• Datenstruktur der Prioritätswarteschlange in C ++ mit Abbildung
• Doppelt verknüpfte Listendatenstruktur in C ++ mit Abbildung