Kann die B + Baumsuche besser abschneiden als die Binärsuchbaumsuche, bei der alle Schlüssel-Daten der Blattknoten im Speicher sind?

Question

Angenommen, wir implementieren einen B + -Baum im Speicher, Schlüssel befinden sich an den internen Knoten und Schlüssel-Daten-Paare befinden sich in den Blattknoten. Wenn B + Baum mit einem Fan-Out f, bedeutet dies, dass B + Baum eine Höhe von log_f N haben wird, wobei N die Anzahl der Schlüssel ist, während die entsprechende BST Höhe von log_2 N haben wird. Wenn wir nicht tun Disk liest und schreibt, kann die B + Baumsuchleistung besser sein als die Suchleistung der Binärsuche? Wie? Da für B + Baum an jedem internen Knoten haben wir eine Entscheidung über F viele Entscheidungen statt, wenn 1 für BST?

Answer 1

Zumindest im Vergleich zum Cache hat der Hauptspeicher viele der gleichen Eigenschaften wie ein Festplattenlaufwerk - es hat eine ziemlich hohe Bandbreite, aber viel höhere Latenz als Cache. Es hat eine ziemlich große minimale Lese-Größe und gibt wesentlich höhere Bandbreite, wenn Lesevorgänge vorhersagbar sind (z.B. wenn Sie eine Anzahl einer Anzahl von Cache-Zeilen an zusammenhängenden Adressen lesen). Als solches profitiert es von den gleichen Optimierungsmöglichkeiten (obwohl die Details oft ein wenig variieren).

B-Bäume (und Varianten wie B * und B + Bäume) wurden explizit entworfen, um gut mit den Zugriffsmustern zu funktionieren, die von Laufwerken gut unterstützt werden. Da Sie sowieso eine ziemlich große Menge an Daten lesen müssen, können Sie die Daten genauso gut packen, um die Menge zu maximieren, die Sie aus dem Speicher, den Sie lesen müssen, erhalten. In beiden Fällen erhalten Sie auch häufig einen beträchtlichen Bandbreitengewinn, indem Sie ein Vielfaches des minimalen Lesewerts in einem vorhersagbaren Muster lesen (insbesondere eine Anzahl von aufeinanderfolgenden Lesevorgängen an aufeinanderfolgenden Adressen). Daher ist es oft sinnvoll, die Größe einer einzelnen Seite auf etwas zu erhöhen, das größer ist als das Minimum, das Sie gleichzeitig lesen können.

Ebenso können wir in beiden Fällen das Absteigen durch mehrere Ebenen von Knoten im Baum planen, bevor wir die Daten finden, die uns wirklich interessieren. Ähnlich wie beim Lesen von der Festplatte profitieren wir von der Maximierung der Dichte der Schlüssel in den Daten, die wir lesen, bis wir tatsächlich die Daten gefunden haben, die uns wichtig sind. Mit einem typischen binären Baum:

... lesen wir eine Reihe von Daten, für die wir keine wirkliche Verwendung haben Nur wenn wir den richtigen Schlüssel gefunden haben, möchten/wollen wir die zugehörigen Daten erhalten. In Fairness, können wir das mit einem binären Baum tun als auch mit nur einer relativ geringen Modifikationen an die Knotenstruktur:

template <class T, class U> 
struct node { 
    T key; 
    U *data; 
    node *left; 
    node *right; 
}; 

nun der Knoten enthält nur einen Zeiger auf die Daten, anstatt die Daten selbst. Dies wird nichts erreichen, wenn data klein ist, aber kann viel erreichen, wenn es groß ist.

Zusammenfassung: aus dem Blickwinkel der CPU, Lesevorgänge aus dem Hauptspeicher haben die gleichen grundlegenden Eigenschaften wie liest von Festplatte; Eine Festplatte zeigt nur eine extremere Version dieser Eigenschaften. Daher gelten die meisten Entwurfsüberlegungen, die zum Entwurf von B-Bäumen (und Varianten) geführt haben, in ähnlicher Weise für Daten, die im Hauptspeicher gespeichert sind.

B-Bäume funktionieren gut und bieten oft erhebliche Vorteile, wenn sie für In-Memory-Speicher verwendet werden.