StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POB+ tree implementation, * * vs *
text
Body
copied!<p>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:</p> <pre><code>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; }; </code></pre> <p>As you can see my current implementation is using * * in the place where I am wondering whether I should use * * or *.</p> <p>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.</p> <p>With **</p> <pre><code>someFunction(BPlusNode* currNode) { ...... someFunction(currNode->children[ChildIndex]); } </code></pre> <p><br><br> with *</p> <pre><code>someFunction(BPlusNode* currNode) { ...... someFunction((currNode->children) + ChildIndex); } </code></pre> <p>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).</p> <p>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?</p> <p>Edit:<br> 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.</p> <p>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.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload