B+ Tree ist eine Erweiterung von B Tree, die effiziente Einfüge-, Lösch- und Suchvorgänge ermöglicht.
Im B-Baum können Schlüssel und Datensätze sowohl im internen als auch im Blattknoten gespeichert werden. Im B+-Baum hingegen können Datensätze (Daten) nur auf den Blattknoten gespeichert werden, während interne Knoten nur die Schlüsselwerte speichern können.
Index von Java
Die Blattknoten eines B+-Baums werden in Form einfach verknüpfter Listen miteinander verknüpft, um die Suchabfragen effizienter zu gestalten.
B+ Tree werden zum Speichern großer Datenmengen verwendet, die nicht im Hauptspeicher gespeichert werden können. Da die Größe des Hauptspeichers immer begrenzt ist, werden die internen Knoten (Schlüssel zum Zugriff auf Datensätze) des B+-Baums im Hauptspeicher gespeichert, während die Blattknoten im Sekundärspeicher gespeichert werden.
Die internen Knoten des B+-Baums werden oft als Indexknoten bezeichnet. In der folgenden Abbildung ist ein B+-Baum der Ordnung 3 dargestellt.
Vorteile von B+ Tree
- Datensätze können in der gleichen Anzahl von Festplattenzugriffen abgerufen werden.
- Die Höhe des Baumes bleibt ausgeglichen und im Vergleich zum B-Baum geringer.
- Wir können sowohl sequentiell als auch direkt auf die in einem B+-Baum gespeicherten Daten zugreifen.
- Zur Indizierung werden Schlüssel verwendet.
- Schnellere Suchanfragen, da die Daten nur auf den Blattknoten gespeichert werden.
B-Baum VS. B+-Baum
| SN | B Baum | B+ Baum |
|---|---|---|
| 1 | Suchschlüssel können nicht wiederholt gespeichert werden. | Es können redundante Suchschlüssel vorhanden sein. |
| 2 | Daten können sowohl in Blattknoten als auch in internen Knoten gespeichert werden | Daten können nur auf den Blattknoten gespeichert werden. |
| 3 | Die Suche nach einigen Daten ist ein langsamerer Prozess, da Daten sowohl auf internen Knoten als auch auf den Blattknoten gefunden werden können. | Die Suche ist vergleichsweise schneller, da Daten nur auf den Blattknoten gefunden werden können. |
| 4 | Das Löschen interner Knoten ist sehr kompliziert und zeitaufwändig. | Das Löschen wird niemals ein komplexer Prozess sein, da Elemente immer von den Blattknoten gelöscht werden. |
| 5 | Blattknoten können nicht miteinander verknüpft werden. | Blattknoten sind miteinander verknüpft, um die Suchvorgänge effizienter zu gestalten. |
Einfügen in den B+-Baum
Schritt 1: Fügen Sie den neuen Knoten als Blattknoten ein
Schritt 2: Wenn das Blatt nicht über den erforderlichen Platz verfügt, teilen Sie den Knoten und kopieren Sie den mittleren Knoten auf den nächsten Indexknoten.
Kajal Aggarwal
Schritt 3: Wenn der Indexknoten nicht über den erforderlichen Platz verfügt, teilen Sie den Knoten und kopieren Sie das mittlere Element auf die nächste Indexseite.
Beispiel :
Fügen Sie den Wert 195 in den in der folgenden Abbildung gezeigten B+-Baum der Ordnung 5 ein.
195 wird nach 190 in den rechten Teilbaum von 120 eingefügt. Fügen Sie es an der gewünschten Position ein.
Der Knoten enthält mehr als die maximale Anzahl an Elementen, d. h. 4. Teilen Sie ihn daher auf und platzieren Sie den Medianknoten bis zum übergeordneten Knoten.
Jetzt enthält der Indexknoten 6 untergeordnete Knoten und 5 Schlüssel, was die Eigenschaften des B+-Baums verletzt. Daher müssen wir ihn aufteilen, wie folgt.
Löschung im B+-Baum
Schritt 1: Löschen Sie den Schlüssel und die Daten aus den Blättern.
„Banker-Algorithmus“
Schritt 2: Wenn der Blattknoten weniger als die Mindestanzahl an Elementen enthält, führen Sie den Knoten nach unten mit seinem Geschwisterknoten zusammen und löschen Sie den Schlüssel dazwischen.
Schritt 3: Wenn der Indexknoten weniger als die Mindestanzahl an Elementen enthält, führen Sie den Knoten mit dem Geschwisterknoten zusammen und verschieben Sie den Schlüssel dazwischen nach unten.
Beispiel
Löschen Sie den Schlüssel 200 aus dem in der folgenden Abbildung gezeigten B+-Baum.
200 ist im rechten Teilbaum von 190 vorhanden, nach 195. Löschen Sie es.
Führen Sie die beiden Knoten zusammen, indem Sie 195, 190, 154 und 129 verwenden.
Jetzt ist Element 120 das einzelne Element im Knoten, das die B+-Baumeigenschaften verletzt. Daher müssen wir es mit 60, 78, 108 und 120 zusammenführen.
Jetzt wird die Höhe des B+-Baums um 1 verringert.
