B+ tree implementation, * * vs *

Question

I am writing a B+ tree for a variety of reasons and I am come here to ask a question about implementation of its nodes. My nodes currently look like:

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;
};

As you can see my current implementation is using * * in the place where I am wondering whether I should use * * or *.

I am well aware of the fact that * * requires two dereference operations and thus is a slower than simply using *, however this class uses a great deal of recursion and it is far more convienient to pass pointers to sub calls of recursive functions. To do this with * I would need to do pointer arithmetic and pass the resulting pointer.

With **

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

with *

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

I can see that there is an additional read of memory to produce the pointer desired in the * * version, but the * * version is also easier to think about for me (it conforms more closely to how I see the diagrams drawn in "The Art of Computer Programming" and on wikipedia).

Does anyone have any thoughts one way or the other? Suggestions for a third option? Proof of why one is superior to the other? etc?

Edit:
I might post this as an answer below but I just realized that with the * * scheme I do not need to copy the entire contents of each subnode or bucket should I want to insert one into the middle of the array (ie resize the array). If there are 20 subnodes for the * scheme when I reallocate the array I would need to copy 20*sizeof(BPlusNode) bytes, as opposed to 20*sizeof(BPlusNode*) bytes for the * * scheme.

On the other hand it has occurred to me that since I perform all the inserts and page splits are done up front maybe this increased efficiency in performing them is unnecessary, and the benefits of * over * * in searches outweighs it.

Answer 1

Using **, you need an extra allocation step to hold each BPlusNode* child pointer. Or you could allocate a block of them and just have each pointer in children point to sequential BPlusNode* elements inside this block -- but it's still one extra dynamic memory allocation per node creation (and a corresponding extra deallocation step on destruction). So I would absolutely recommend using a single *. If writing

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

hurts you, you can rewrite it as

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

which I find clearer.

Answer 2

I would define another struct for the key and pointer data. I would commit to using fixed size nodes which should match your on-disk structure. This makes memory mapping the tree a lot easier.

Your BPlusNode struct becomes a handle class that points to these mapped data nodes and synthesizes the things like prev and next pointers by reading the siblings as it descends the tree.

It could look something like the following:

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 3

Would you be better off using STL 'vector<keyType *> keys' and 'vector<BPlusNode *> children', and so on?

It might be too simplistic, but my impression is that double-indirection is not often needed in C++ (and not all that often in C, though more often than in C++).