Ich schreibe ein Programm, um die Anzahl der Objekte innerhalb eines bestimmten Bereichs abzurufen, und ich verwende die B-Baum-Datenstruktur, um meine Lösung zu implementieren, da die Anzahl der Objekte nicht in RAM passen kann . Ich stieß auf mehrere Artikel, die besagen, dass B + -Bäume für Bereichsabfragen weit besser sind als B-Bäume und von allen wichtigen Datenbankimplementierungen verwendet werden. Ich konnte nicht verstehen, warum B + -Bäume besser als B-Bäume sind, da alle Daten auf dem Blatt gespeichert sind und es h (Baumhöhen) Plattenzugriffe benötigt, um den Knoten abzurufen und die Bereichsabfrage durchzuführen, während im B-Baum das Intervall liegt kann auf Elternknoten angeordnet sein, und die Plattenzugriffe wären somit minimiert. Außerdem kann ich, wenn ich eine Abfrage habe, wie beispielsweise die Anzahl der Objekte eines bestimmten Schlüssels, den Schlüssel finden, bevor ich wie bei B + Bäumen den ganzen Weg hinunter zu den Blättern abfahre. Warum sagen sie dann, dass B + -Bäume für Bereichsabfragen effizienter sind als B-Bäume? Wenn ich ein Programm schreiben muss, um Bereichsabfragen durchzuführen, sollten nicht B-Bäume die richtige Datenstruktur sein? Vielen Dank im Voraus für Ihre Antworten!Bereichsabfragen mit B-Bäumen und B + -Bäumen
Antwort
Praktische B-Baum- und B + Baum-Implementierungen neigen dazu, Knoten einer festen Bytegröße zu haben, die so gewählt werden, dass sie der Seitengröße der Architektur oder eines anderen Geräts wie der Clustergröße auf der Festplatte entsprechen. Ein typischer Wert wäre 4096 Bytes.
Ein B + -Baum kann viele weitere Schlüssel in einen internen Knoten einfügen, da für die Datensatzdaten kein Platz benötigt wird. Dies ergibt einen höheren Fanout (niedrigere Baumhöhe) und eine bessere Cache-Nutzung, da eine gegebene Menge von Indexseiten (interne Knoten) mehr Abfragen "abdeckt", als dies bei einem B-Baum der Fall wäre.
Ein zweiter Vorteil von B + -Bäumen ist, dass die Schlüssel in internen Knoten nur für Routing-Suchvorgänge zum rechten Blatt benötigt werden. Sie müssen nur die Dinge auf der linken Seite von den Dingen auf der rechten Seite trennen, aber sie müssen nicht mit den tatsächlichen Schlüsseln übereinstimmen. Dies bedeutet, dass sie oft verkürzt werden können, und es bedeutet auch, dass Löschungen nicht von der Blattschicht in die Indexschicht übertragen werden müssen (dh wenn Sie einen Schlüssel aus einem Blatt gelöscht haben, sind Sie fertig - keine Notwendigkeit um alles von internen Knoten zu löschen, mit Ausnahme dessen, was während der Neuausrichtung natürlich passiert).
In einem typischen B + -Baum haben die Blattknoten auch Zeiger auf ihre linken und rechten Geschwister. Dies bedeutet, dass Sie über eine Reihe von Datensätzen iterieren können, indem Sie eine verknüpfte Liste von Seiten durchlaufen, anstatt die für B-Bäume typische knifflige Iterationslogik verwenden zu müssen.
in dem B-Baum das Intervall so
würde auf übergeordneten Knoten und die Plattenzugriffe angeordnet sein kann
minimiert diese Theorie zur Ruhe zu legen, abzuschätzen, wie viele Schlüssel GESAMT in internen Knoten angeordnet sind, ein B-Baum und wie viele Schlüssel insgesamt in Blattknoten liegen. Dieses Verhältnis sagt Ihnen, wie oft eine Suche früh anhalten kann, bevor sie den gesamten Weg bis zur Blattebene zurücklegt. Hinweis: Das Frühaktionsszenario gilt nur für Abfragen, bei denen der Schlüssel exakt im Baum vorhanden ist. ansonsten ist eine angemessene bis zur Blattebene unvermeidlich.