Wo sind die Werte für B-Tree Schlüssel gespeichert?

Question

Ich habe studiert B-Bäume für die Speicherung von etwa 10k Strings-Datenbank jede Zeichenfolge mit einer eindeutigen ID, die ich denke, kann als mein Schlüssel handeln. Aber jede Implementierung, die ich gesehen habe, zeigt nur Schlüssel in einem B-Baum, nicht die Werte. Ich bin sicher, dass B-Tree, wenn er als Karte fungiert, Werte mit Schlüsseln verknüpfen muss, aber ich kann nicht verstehen, ob sie innerhalb des Knotens des Baums zusammen mit einem Schlüssel gespeichert wurden. Beispielsweise.

 ||key3| |key6|| 
    /  |   \ 
    / ||key4| |key5|| \ 
/      \ 
||key1| |key2||   ||key7| |key8|| 

---

 ||k3,v3| |k6,v6|| 
    /  |   \ 
    / ||k4,v4||k5,v5|| \ 
/      \ 
||k1,v1| |k2,v2||   ||k7,v7| |k8,v8|| 

Ich bin nicht sicher, wie und wo die Werte gespeichert sind.

Answer 1

In jedem einzelnen Knoten, sowohl interne und Blatt, zusammen mit Schlüsseln.

In einem B + -Tree sind alle Schlüssel in Blattknoten verfügbar. Wenn Sie also einen Blattknoten aufteilen, können Sie die Schlüssel nur an Ihre Eltern übergeben und die Werte für sich behalten. In einem B-Baum wiederholen sich die Schlüssel jedoch nicht, Sie müssen also Werte in internen Knoten haben.

Sie können eine Schlüssel/Wert-Map verwenden und bei baumspezifischen Funktionen über ihren Schlüssel iterieren. Da Sie Ihre Schlüssel sortiert halten müssen, sollten Sie eine sortierte Map verwenden, wie TreeMap in Java oder einfache std :: map für C++. (Python hat so etwas in der Standardbibliothek nicht.) Sie helfen auch dabei, einen Knoten einfach aufzuteilen und Dinge auf einen neuen Knoten zu übertragen.