Umsetzung des B+-Baums, * * vs *

Question

Ich schreibe einen B+ Baum aus verschiedenen Gründen und bin hierher gekommen, um eine Frage zur Implementierung seiner Knoten zu stellen. Meine Knoten sehen derzeit wie folgt aus:

struct BPlusNode
{
public:
    //holds the list of keys
    keyType **keys;
    //stores the number of slots used
    size_t size;
    //holds the array of pointers to lower nodes NULL if this is a leaf node
    BPlusNode **children;
    //holds the pointer to the next load to the 'left'
    BPlusNode *next;
    //Data page pointers NULL if this is a branch node
    Bucket **pages;
};

Wie Sie sehen können, verwendet meine aktuelle Implementierung * * an der Stelle, an der ich mich frage, ob ich * * oder * verwenden sollte.

Ich bin mir der Tatsache bewusst, dass * * zwei Dereferenzierungsoperationen erfordert und daher langsamer ist als die Verwendung von *, aber diese Klasse verwendet sehr viele Rekursionen, und es ist viel bequemer, Zeiger an Unteraufrufe rekursiver Funktionen zu übergeben. Um dies mit * zu tun, müsste ich eine Zeigerarithmetik durchführen und den resultierenden Zeiger übergeben.

Mit **

someFunction(BPlusNode* currNode)
{
    ......
    someFunction(currNode->children[ChildIndex]);
}

mit *

someFunction(BPlusNode* currNode)
{
    ......
    someFunction((currNode->children) + ChildIndex);
}

Ich kann sehen, dass es ein zusätzliches Lesen des Speichers gibt, um den Zeiger zu erzeugen, der in der * * Version gewünscht wird, aber die * * Version ist auch einfacher für mich zu denken (sie entspricht eher den Diagrammen, die ich in "The Art of Computer Programming" und auf Wikipedia sehe).

Hat jemand eine Idee für die eine oder andere Seite? Vorschläge für eine dritte Option? Beweise dafür, warum die eine der anderen überlegen ist? usw.?

Edit :
Ich könnte dies als Antwort unten posten, aber ich habe gerade festgestellt, dass ich mit dem * * Schema nicht den gesamten Inhalt jedes Unterknotens oder Buckets kopieren muss, wenn ich einen in der Mitte des Arrays einfügen möchte (d.h. die Größe des Arrays ändern). Wenn es 20 Unterknoten für das * Schema gibt und ich das Array neu zuordne, müsste ich 20*sizeof(BPlusNode) Bytes kopieren, im Gegensatz zu 20*sizeof(BPlusNode*) Bytes für das * * Schema.

Andererseits kam mir der Gedanke, dass, da ich alle Einfügungen und Seitenteilungen im Voraus durchführe, diese erhöhte Effizienz bei der Durchführung vielleicht unnötig ist und die Vorteile von * gegenüber * * bei der Suche überwiegen.

Answer 1

Ich würde eine weitere Struktur für die Schlüssel- und Zeigerdaten definieren. Ich würde mich auf die Verwendung von Knoten fester Größe festlegen, die mit der Struktur auf der Festplatte übereinstimmen sollten. Das macht die Speicherzuordnung des Baums viel einfacher.

Ihre BPlusNode-Struktur wird zu einer Handle-Klasse, die auf diese gemappten Datenknoten verweist und Dinge wie prev- und next-Zeiger synthetisiert, indem sie die Geschwister liest, während sie den Baum absteigt.

Sie könnte etwa wie folgt aussehen:

enum BPlusNodeType {
    LEAF, BRANCH
};

struct BPlusNodeData {
    static const size_t max_size = 511; // Try to fit into 4K? 8K?
    uint16_t size;
    uint16_t type;
    keyType key[max_size];
    union {
        Bucket* data[max_size];
        BPlusNodeData* children[max_size];
    };
};

Answer 2

使用方法 ** benötigen Sie einen zusätzlichen Zuweisungsschritt, um jede BPlusNode* Kinderzeiger. Oder Sie könnten einen Block von ihnen zuweisen und einfach jeden Zeiger in children zeigen auf sequenzielle BPlusNode* Elemente innerhalb dieses Blocks - aber es ist immer noch eine zusätzliche dynamische Speicherzuweisung pro Knoten Erstellung (und eine entsprechende zusätzliche Deallokation Schritt auf Zerstörung). Ich würde also unbedingt empfehlen, einen einzigen * . Wenn das Schreiben

someFunction((currNode->children) + ChildIndex);

schadet, können Sie es umschreiben in

someFunction(&currNode->children[ChildIndex]);

was ich klarer finde.

Answer 3

Wäre es besser, STL zu verwenden ' vector<keyType *> keys ' und ' vector<BPlusNode *> children ', und so weiter?

Vielleicht ist es zu einfach, aber ich habe den Eindruck, dass die doppelte Richtung in C++ nicht oft benötigt wird (und in C auch nicht so oft, wenn auch häufiger als in C++).