B+ Baum
B+ Baum | |||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Typ | Baum (Datenstruktur) | ||||||||||||||||||||
Zeitkomplexität in Big O Notation | |||||||||||||||||||||
|
A B+ Baum ist ein M-Ary-Baum mit einer variablen, aber oft großen Anzahl von Kindern pro Knoten. Ein B+ Baum besteht aus einer Wurzel, inneren Knoten und Blättern.[1] Die Wurzel kann entweder ein Blatt oder ein Knoten mit zwei oder mehr Kindern sein.
Ein B+ -Baum kann als a betrachtet werden B-Baum in dem jeder Knoten nur Schlüssel (nicht Schlüssel -Wert -Paare) enthält und zu denen unten mit verknüpften Blättern ein zusätzliches Niveau hinzugefügt wird.
Der Hauptwert eines B+ -Baums besteht darin, Daten zum effizienten Abrufen in a zu speichern blockorientiert Speicherkontext - insbesondere, Dateisysteme. Dies liegt in erster Linie dessen im Gegensatz zu Binäre SuchbäumeB+ Bäume haben einen sehr hohen Fanout (Anzahl der Zeiger auf Kinderknoten in einem Knoten,[1] Typischerweise in der Größenordnung von 100 oder mehr), wodurch die Anzahl der E/A -Operationen reduziert wird, die erforderlich sind, um ein Element im Baum zu finden.
Geschichte
Es gibt kein einzelnes Papier, das das B+ -Baumkonzept einführt. Stattdessen wird der Begriff, alle Daten in Blattknoten aufrechtzuerhalten, wiederholt als interessante Variante hervorgebracht. Douglas Comer Anmerkungen in einer frühen Umfrage unter B-Bäumen (die auch B+ Bäume abdeckt), dass der B+ -Baum bei IBMs verwendet wurde Vsam Datenzugriffssoftware und bezieht sich auf einen IBM veröffentlichten Artikel aus dem Jahr 1973.[2]
Struktur
Wie bei anderen Bäumen können B+ Bäume als Sammlung von drei Arten von Knoten dargestellt werden: Wurzel, intern, und Blatt. Diese Knotentypen haben die folgenden Eigenschaften:[3]
- Einzelne Knoten haben entweder Schlüssel oder Kinder, aber niemals beide gleichzeitig: Dies ist die Hauptunterscheidung von a B-Baum.
- Das bestellen oder Verzweigungsfaktor b Von einem B+ -Baum misst die Kapazität interner Knoten, d. H. Ihre maximal zulässige Anzahl direkter untergeordneter Knoten. Dieser Wert ist über den gesamten Baum konstant.
- Interne Knoten haben keine Schlüssel, haben aber immer Kinder ungleich Null. Das tatsächlich Anzahl der Kinder m Für einen bestimmten internen Knoten ist so eingeschränkt, dass . Jedes Kind wird dann als als bezeichnet zum , wo repräsentiert den Kinderknoten bei natürliche Zahl Index .
- Blattknoten haben keine Kinder und enthalten stattdessen die Elemente des B+ -Baums als Schlüssel. Die Anzahl der Schlüssel n In einem bestimmten Blattknoten enthalten muss die doppelte Ungleichheit erfüllen .
- Die Wurzel wird typischerweise als eine spezielle Art von internem Knoten angesehen, der möglicherweise nur 2 Kinder hat.[1] Dies bedeutet . Zum Beispiel, wenn die Bestellung b eines b+ baums beträgt 7, jeder interne Knoten kann dazwischen haben und 7 Kinder, während die Wurzel zwischen 2 und 7 haben kann.
- In der Situation, in der ein B+ -Baum leer ist oder genau 1 Knoten enthält, wird die Wurzel stattdessen zum einzelnen Blatt. In diesem Fall die Anzahl der Schlüssel n muss befriedigen .
Ein konkretes Beispiel für diese Grenzen ist in der folgenden Tabelle dargestellt:
Knotentyp | Kinder Typ | Min Anzahl der Kinder | Maximale Anzahl von Kindern | Beispiel | Beispiel |
---|---|---|---|---|---|
Wurzelknoten (wenn er der einzige Knoten im Baum ist) | Aufzeichnungen | 0 | 0–6 | 0–99 | |
Wurzelknoten | Interne Knoten oder Blattknoten | 2 | b | 2–7 | 2–100 |
Interner Knoten | Interne Knoten oder Blattknoten | b | 4–7 | 50–100 | |
Blattknoten | Aufzeichnungen | 4–7 | 50–100 |
Intervalle in internen Knoten

Per Definition ist jeder im B+ -Baum enthaltene Wert eine Schlüssel, die in genau einem Blattknoten enthalten ist. Jeder Schlüssel muss direkt sein vergleichbar mit jedem anderen Schlüssel, der a bildet Gesamtbestellung.[4] Dies ermöglicht jedem Blattknoten, alle Tasten zu jeder Zeit sortiert zu halten, wodurch jeder interne Knoten eine geordnete Sammlung von erstellt wird Intervalle Darstellung des zusammenhängenden Ausmaßes der in einem gegebenen Blatt enthaltenen Werte. Interne Knoten im Baum können dann ihre eigenen Intervalle konstruieren, die die Intervalle, die in ihren eigenen internen Knoten enthalten sind, rekursiv zusammenhängen. Schließlich repräsentiert die Wurzel eines B+ -Baums den gesamten Wertebereich im Baum, wobei jeder interne Knoten ein Subinterval darstellt.
Damit diese rekursiven Intervallinformationen aufbewahrt werden sollen, müssen interne Knoten zusätzlich enthalten Kopien von Schlüssel zum Darstellung des geringsten Elements innerhalb des vom Kindes mit Index abgedeckten Intervall i (was selbst ein interner Knoten oder ein Blatt sein kann).
Eigenschaften
Für ein b-Bestellung B+ Baum mit h Indexniveaus:
- Die maximale Anzahl der gespeicherten Datensätze ist
- Die Mindestanzahl der gespeicherten Datensätze ist
- Die Mindestanzahl von Schlüssel ist
- Die maximale Anzahl von Schlüssel ist
- Der Platz, der für die Speicherung des Baumes erforderlich ist, ist
- Das Einfügen einer Aufzeichnung erfordert erforderlich Operationen
- Das Finden eines Rekords erfordert erforderlich Operationen
- Das Entfernen eines (zuvor lokalisierten) Datensatzes erfordert Operationen
- Ausführen a Bereichsabfrage mit k Elemente, die innerhalb des Bereichs auftreten Operationen
- Die B+ -Baumstruktur erweitert/Verträge als Anzahl von Aufzeichnungen Erhöht/nimmt ab. Es gibt keine Einschränkungen für die Größe von B+ -Bäumen. Die zunehmende Benutzerfreundlichkeit von a Datenbanksystem.
- Jede Änderung der Struktur hat keine Auswirkungen auf die Leistung aufgrund ausgewogener Baumeigenschaften.[5]
- Die Daten werden in den Blattknoten gespeichert, und mehr Verzweigungen der internen Knoten hilft, die Höhe des Baumes zu verringern und somit die Suchzeit zu verkürzen. Infolgedessen funktioniert es in sekundären Speichergeräten gut.[6]
- Die Suche wird extrem einfach, da alle Datensätze nur im Blattknoten gespeichert sind und nacheinander in der verlinkten Liste sortiert werden.
- Wir können Reichweite oder teilweise Abruf mit B+ -Baum abrufen. Dies wird einfacher und schneller durch Überqueren der Baumstruktur erleichtert. Mit dieser Funktion wird die B+ -Baumstruktur in vielen Suchmethoden angewendet.[5]
Algorithmen
Suche
Wir suchen einen Wert k im B+ Baum. Dies bedeutet, dass wir von der Wurzel nach dem Blatt suchen, das den Wert enthalten kann k. Bei jedem Knoten finden wir heraus, welcher internen Knoten wir folgen sollten. Ein interner B+ -Baumknoten hat höchstens Kinder, wo jeder von ihnen ein anderes Subinterval darstellt. Wir wählen das entsprechende Kind über eine lineare Suche von der aus m Einträge, wenn wir endlich zu einem Blatt kommen, suchen wir eine lineare Suche nach seiner n Elemente für den gewünschten Schlüssel. Weil wir nur einen Zweig aller Kinder an jedem Baumbereich durchqueren, erreichen wir Laufzeit, wo N Ist die Gesamtzahl der Schlüssel, die in den Blättern des B+ -Baums gespeichert sind.[3]
Funktion Suche(k, Wurzel) ist Lassen Leaf = Leaf_search (k, Wurzel) zum Leaf_key in Leaf.keys (): wenn K = Leaf_key: Rückkehr Stimmt Rückkehr FALSCH
Funktion Leaf_search (k, Knoten) ist wenn Knoten ist ein Blatt: Rückkehr Knoten Lassen p = node.children () Lassen l = node.left_sided_intervals () behaupten Lassen m = p.len () zum i aus 1 zu m - 1: wenn : Rückkehr Leaf_search (k, p [i]) Rückkehr Leaf_search (k, p [m])
Beachten Sie, dass dieser Pseudocode eine 1-basierte Array-Indexierung verwendet.
Einfügen
- Führen Sie eine Suche durch, um zu bestimmen, in welchen Bucket der neue Datensatz gehen sollte.
- Wenn der Eimer nicht voll ist (höchstens Einträge nach der Einfügung) fügen Sie den Datensatz hinzu.
- Andernfalls, Vor Einfügen des neuen Rekords
- Teilen Sie den Eimer.
- Der ursprüngliche Knoten hat ⎡ (l+1)/2⎤ Elemente
- Der neue Knoten hat ⎣ (l+1)/2⎦ Elemente
- Kopieren Sie ⎡ (l+1)/2⎤-ten Schlüssel zum übergeordneten Taste und fügen Sie den neuen Knoten zum übergeordneten Einsatz ein.
- Wiederholen Sie, bis ein Elternteil festgestellt wird, dass sie nicht geteilt werden müssen.
- Fügen Sie den neuen Datensatz in den neuen Knoten ein.
- Teilen Sie den Eimer.
- Wenn sich die Wurzel spaltet, behandeln Sie es so, als hätte sie ein leeres Elternteil und spalten Sie sie oben.
B-Bäume wachsen an der Wurzel und nicht an den Blättern.[1]
Massenladung
Bei einer Sammlung von Datensätzen möchten wir einen B+ -Baumindex auf einem Schlüsselfeld erstellen. Ein Ansatz besteht darin, jeden Datensatz in einen leeren Baum einzufügen. Es ist jedoch ziemlich teuer, da jeder Eintrag von der Wurzel von der Wurzel starten und zur entsprechenden Blattseite gehen muss. Eine effiziente Alternative ist die Verwendung von Schüttgütern.
- Der erste Schritt besteht darin, die Dateneinträge nach einem Suchschlüssel in aufsteigender Reihenfolge zu sortieren.
- Wir weisen eine leere Seite zur Verfügung, um als Stamm zu dienen, und fügen einen Zeiger auf die erste Seite der Einträge ein.
- Wenn das Root voll ist, teilen wir das Root auf und erstellen eine neue Root -Seite.
- Fügen Sie weiterhin Einträge in die richtige Indexseite direkt über der Blattebene ein, bis alle Einträge indiziert sind.
Notiz :
- Wenn sich die rechtsmächtige Indexseite über der Blattpegel füllt, wird sie aufgeteilt.
- Diese Aktion kann wiederum einen Schritt näher an der Stamme näher auf die rechte Indexseite aufgeteilt werden.
- Spaltungen treten nur auf dem rechten Weg von der Wurzel bis zur Blattebene auf.[7]
Streichung
Der Zweck des Löschalgorithmus besteht darin, den gewünschten Eingangsknoten aus der Baumstruktur zu entfernen. Wir rekursiv Rufen Sie den Löschalgorithmus auf dem entsprechenden Knoten an, bis kein Knoten gefunden wurde. Für jeden Funktionsaufruf überqueren wir mit dem Index, um zu navigieren, bis wir den Knoten finden, ihn entfernen und dann wieder auf die Wurzel arbeiten.
Bei der Eingabe l möchten wir entfernen:
- Wenn l mindestens halb voll ist, fertig
-Wenn L nur D-1-Einträge hat, versuchen Sie, sich von Geschwistern zu leihen (benachbarter Knoten mit demselben Elternteil wie L).
Nachdem die Neuverteilung zweier Geschwisterknoten aufgetreten ist, muss der übergeordnete Knoten aktualisiert werden, um diese Änderung widerzuspiegeln. Der Indexschlüssel, der auf das zweite Geschwister hinweist, muss den kleinsten Wert dieses Knotens als Indexschlüssel betrachten.
- Wenn neu eingestuft wird, fusionieren Sie L und Geschwister. Nach dem Zusammenführen wird der übergeordnete Knoten aktualisiert, indem der Indexschlüssel gelöscht wird, der auf den gelöschten Eintrag hinweist. Mit anderen Worten, wenn Merge eingetreten ist, muss der Eintrag (auf L oder Geschwister zeigen) von Eltern von L.
HINWEIS: Die Zusammenführung kann sich zur Wurzel ausbreiten, was bedeutet, dass die Höhe abnimmt.[8]

Implementierung
Die Blätter (die untersten Indexblöcke) des B+ -Baums sind in einer verknüpften Liste häufig miteinander verbunden. Dadurch wird die Reichweite oder eine (geordnete) Iteration durch die Blöcke einfacher und effizienter (obwohl die oben genannte Obergrenze auch ohne diese Ergänzung erreicht werden kann). Dies erhöht den Raumverbrauch oder die Wartung am Baum nicht wesentlich. Dies zeigt einen der wesentlichen Vorteile eines B+-Baums gegenüber einem B-Baum; In einem B-Baum, da nicht alle Schlüssel in den Blättern vorhanden sind, kann eine solche geordnete verlinkte Liste nicht konstruiert werden. Ein B+-Baum ist daher als Datenbanksystemindex besonders nützlich, wobei die Daten typischerweise auf der Festplatte liegen, da der B+-Baum tatsächlich eine effiziente Struktur für die Unterbringung der Daten selbst bereitstellt (dies wird in beschrieben[9]: 238 als Indexstruktur "Alternative 1").
Wenn ein Speichersystem eine Blockgröße von B -Bytes hat und die zu gespeicherten Schlüssel eine Größe von k haben, ist der wohl effizienteste B+ -Baum einer wo, wo . Obwohl theoretisch die einmalige Einheit unnötig ist, wird in der Praxis oft ein wenig zusätzlicher Platz von den Indexblöcken einbezogen (z. B. die verknüpften Listenreferenzen in den Blattblöcken). Ein Indexblock, der etwas größer ist als der tatsächliche Block des Speichersystems, ist eine erhebliche Leistungsabnahme; Daher ist auf der Seite der Vorsicht vorzuziehen.
Wenn Knoten des B+ -Baums als Elementarrays organisiert sind, kann es eine beträchtliche Zeit dauern, ein Element einzufügen oder zu löschen, da die Hälfte des Arrays im Durchschnitt verschoben werden muss. Um dieses Problem zu überwinden, können Elemente in einem Knoten in einem binären Baum oder einem B+ -Baum anstelle eines Arrays organisiert werden.
B+ Bäume können auch für in RAM gespeicherte Daten verwendet werden. In diesem Fall wäre eine angemessene Wahl für die Blockgröße die Größe der Cache -Linie des Prozessors.
Die Weltraumeffizienz von B+ -Bäumen kann durch die Verwendung einiger Kompressionstechniken verbessert werden. Eine Möglichkeit ist die Verwendung Delta -Codierung zum Komprimieren von Schlüssel, die in jedem Block gespeichert sind. Für interne Blöcke kann die Speichereinsparung entweder durch Komprimieren von Schlüsseln oder Zeigern erreicht werden. Für Stringschlüssel kann der Speicherplatz mithilfe der folgenden Technik gespeichert werden: Normalerweise die i-Der Eintrag eines internen Blocks enthält den ersten Schlüssel des Blocks . Anstatt den vollständigen Schlüssel zu speichern, konnten wir das kürzeste Präfix des ersten Blockschlüssels speichern Das ist streng größer (in lexikografischer Reihenfolge) als der letzte Blockschlüssel i. Es gibt auch eine einfache Möglichkeit, Zeiger zu komprimieren: Wenn wir annehmen, dass einige aufeinanderfolgende Blöcke sind zusammenhängend gespeichert, dann reicht es aus, nur einen Zeiger auf den ersten Block und die Anzahl aufeinanderfolgender Blöcke zu speichern.
Alle oben genannten Komprimierungstechniken haben einige Nachteile. Zunächst muss ein voller Block dekomprimiert werden, um ein einzelnes Element zu extrahieren. Eine Technik, um dieses Problem zu überwinden, besteht darin, jeden Block in Unterblocke zu unterteilen und separat zu komprimieren. In diesem Fall muss das Suchen oder Einsetzen eines Elements nur einen Unterblockieren anstelle eines vollen Blocks dekomprimieren oder komprimieren. Ein weiterer Nachteil der Komprimierungstechniken besteht darin, dass die Anzahl der gespeicherten Elemente von einem Block zu einem anderen erheblich variieren kann, je nachdem, wie gut die Elemente in jedem Block komprimiert werden.
Anwendungen
Dateisysteme
Das Reiserfs, NSS, Xfs, JFS, Refs, und BFS Dateisysteme verwenden alle Baumtypen für die Metadatenindizierung. BFS verwendet auch B+ -Bäume zum Speichern von Verzeichnissen. NTFS Verwendet B+ Bäume für Verzeichnis- und Sicherheitsmetadaten-Indexierung. EXT4 verwendet Ausleitungsbäume (eine geänderte B+ -Baumdatenstruktur) für die Dateiausdehnungspezifikation.[10] APFs Verwendet B+ Bäume, um Zuordnungen von Dateisystem -Objekt -IDs an ihren Standorten auf der Festplatte zu speichern und Dateisystemaufzeichnungen (einschließlich Verzeichnisse) zu speichern, obwohl die Blattknoten dieser Bäume keine Geschwisterzeiger haben.[11] Relationale Datenbankverwaltungssysteme wie zum Beispiel IBM DB2,[9] Informix,[9] Microsoft SQL Server,[9] Orakel 8,[9] Sybase Ase,[9] und Sqlite[12] Unterstützen Sie diese Art von Baum für Tabellenindizes. Schlüssel -Wert -Datenbankverwaltungssysteme wie z. Couchdb[13] und Tokyo Kabinett[14] Unterstützen Sie diese Art von Baum für den Datenzugriff.
Datenbanken
Objekte in a finden Hochdimensionale Datenbank Das sind vergleichbar mit einem bestimmten Abfragebobjekt, das eines der am häufigsten verwendeten und dennoch teuren Verfahren in diesen Systemen ist. In solchen Situationen ist es produktiv, den nächsten Nachbarn mit einem B+ -Baum zu finden.[15]
Idistanz
B+ Baum wird effizient verwendet, um eine indizierte Suchmethode namens Idistance zu konstruieren. Die Idistanz sucht nach k nächsten Nachbarn (KNN) in hochdimensionalen metrischen Räumen. Die Daten in diesen hochdimensionalen Räumen sind basierend auf Raum- oder Partitionsstrategien aufgeteilt, und jede Partition hat einen Indexwert, der dem Aspekt der Partition nahe steht. Von hier aus können diese Punkte mit B+ -Baum effizient implementiert werden, sodass die Abfragen auf einzelne Dimensionen kartiert werden. Mit anderen Worten, die Idistanztechnik kann als eine Möglichkeit zur Beschleunigung des sequentiellen Scans angesehen werden. Anstatt Datensätze vom Anfang bis zum Ende der Datendatei zu scannen, startet der Idistanz den Scan von Stellen, an denen die nächsten Nachbarn frühzeitig mit einer sehr hohen Wahrscheinlichkeit erhalten werden können.[16]
NVRAM
Der nichtflüchtige Zufallszugriffsspeicher (NVRAM) hat die B+ -Baumstruktur als Hauptspeicherzugriffstechnik für das Internet of Things (IoT) aufgrund seines nicht statischen Stromverbrauchs und der hohen Solidität des Zellgedächtnisses verwendet. B+ kann den Handel mit Daten zum Gedächtnis effizient regulieren. Darüber hinaus zeigt der B+ -Baum mit fortgeschrittenen Strategien zu Frequenzen einiger stark verwendeter Blatt- oder Referenzpunkte signifikante Ergebnisse zur Erhöhung der Ausdauer von Datenbanksystemen.[17]
Siehe auch
Verweise
- ^ "Der allgegenwärtige B-Tree", ACM Computing Surveys 11 (2): 121–137 (1979).
- ^ a b Pollari-Malmi, Kerttu. ""B+ Bäume"" (PDF). "Informatik, Fakultät für Wissenschaft, Universität Helsinki". p. 3. archiviert von das Original (PDF) am 2021-04-14.
- ^ Mach, Torsten (Sommer 2013). ""Baumstrukturierte Indexierung: ISAM und B+-baum"" (PDF). "Logo der Universität Tübingen Abteilung für Informatik: Datenbanksysteme". p. 84. archiviert von das Original (PDF) am 2021-11-28.
- ^ a b "Datenbanksysteme für erweiterte Anwendungen". Skalierbare Aufteilung massiver Datenströme.
- ^ "[Datenbanksysteme für erweiterte Anwendungen" Aktualisieren Sie die Migration: Ein effizienter B+ -Baum für Flash -Speicher "]". Vorlesungen in Informatik, Band 5982. Springer, Berlin, Heidelberg.
- ^ "ECS 165B: Datenbanksystem -Implementierungsvortrag 6" (PDF). UC Davis CS Abteilung. 9. April 2010. S. 21–23.
- ^ Ramakrishnan, Raghu; Johannes Gehrke (2003). Datenbankmanagementsystem (3. Aufl.). Boston: McGraw-Hill. ISBN 0-07-246563-8. OCLC 49977005.
- ^ a b c d e f Ramakrishnan Raghu, Gehrke Johannes-Datenbankmanagementsysteme, McGraw-Hill Higher Education (2000), 2. Ausgabe (EN) Seite 267
- ^ Giampaolo, Dominic (1999). Praktisches Dateisystemdesign mit dem BE -Dateisystem (PDF). Morgan Kaufmann. ISBN 1-55860-497-9. Archiviert von das Original (PDF) Am 2017-02-13. Abgerufen 2014-07-29.
- ^ "B-Bäume". Apple -Dateisystemreferenz (PDF). Apple Inc. 2020-06-22. p. 122. Abgerufen 2021-03-10.
- ^ SQLite Version 3 Übersicht
- ^ CouchDB -Handbuch (siehe Hinweis nach dem 3. Absatz)
- ^ Tokyo Cabinet Referenz Archiviert 12. September 2009 bei der Wayback -Maschine
- ^ Datenbanksysteme für erweiterte Anwendungen. Japan. 2010.
- ^ Jagadish, H. V.; Ooi, Beng Chin; Tan, Kian-Lee; Yu, cui; Zhang, Rui (Juni 2005). "Idistanz: Eine adaptive B + -Tree -basierte Indexierungsmethode für die nächste Suche nach Nachbarn". ACM -Transaktionen auf Datenbanksystemen. 30 (2): 364–397. doi:10.1145/1071610.1071612. ISSN 0362-5915. S2CID 967678.
- ^ Dharamjeet; Chen, Tseng-yi; Chang, Yuan-Hao; Wu, Chun-Feng; Lee, Chi-Heng; Shih, Wei-kuan (Dezember 2021). "Über Berücksichtigung der Schreibreduzierung hinaus: Ein Verschleiß-Leveling-fähiger B⁺-Tree-Indexierungsschema gegenüber einer NVRAM-basierten Architektur". IEEE-Transaktionen zum computergestützten Design integrierter Schaltkreise und Systeme. 40 (12): 2455–2466. doi:10.1109/tcad.2021.3049677. ISSN 0278-0070. S2CID 234157183.
Externe Links
- B+ Baum in Python, verwendet, um eine Liste zu implementieren
- Dr. Monges B+ Baumindexnotizen
- Bewertung der Leistung von CSB+-baum auf Mutithread-Architekturen
- Einfluss der Knotengröße auf die Leistung von Cache-bewussten B+-baumen
- Fraktales Vorabsteuchen B+-baum
- In Richtung PB+-baum vor Ort: Implementierungen Auswahl und Leistung
- Cache-bewusste Indexstrukturen für Hauptdatenbanken
- Cache unvergesslich B (+)-Bäume
- Die Kraft der B-Bäume: Couchdb B+ Baumimplementierung
- B+ Baumvisualisierung
- B +-baum von Kerttu Pollari-Malmi
- Datenstrukturen B-Bäume und B+ Bäume
Implementierungen
- Interaktive B+ -Baum -Implementierung in C.
- Interaktive B+ -Baum -Implementierung in C ++
- Speicherbasierte B+ -Baumimplementierung als C ++ - Vorlagenbibliothek
- 2019 Verbesserung der vorherigen
- Stream -basierte B+ -Baumimplementierung als C ++ - Vorlagenbibliothek
- Open Source JavaScript B+ Baumimplementierung
- Perl -Implementierung von B+ Bäumen
- Java/C#/Python -Implementierungen von B+ Bäumen
- C# B+ Baum und verwandte "A-List" -Datenstrukturen
- Dateibasierte B+-Baum in C# mit Threading und MVCC -Unterstützung
- Schneller semi-persistentes In-Memory-B+ -Baum in TypeScript/JavaScript, MIT-Lizenz
- JavaScript B+ Baum, MIT -Lizenz
- JavaScript B+ Baum, interaktive und Open Source