StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I've already posted an answer (and since deleted it), but it's possible I've misinterpreted, so here's an answer for another interpretation...</p> <p>What if you need to always know which item is the median in the <em>complete</em> B+ tree container.</p> <p>As amit says, you can keep a pointer (along with your root pointer) to the current leaf node that contains the median. You can also keep an index into that leaf node. So you get O(1) access by following those directly to the correct node and item.</p> <p>The issue is maintaining that. Certainly amit is correct that for each insert, the median must also remain the same item, or must step to the one just before or after. And if you have a linked list through the leaf nodes, that can be handled efficiently even if that means stepping to an adjacent leaf node.</p> <p>I'm not convinced, though, that's it's trivial to determine whether or which way to step, though, except in the special case where the median and the insert happen to be in the same leaf node.</p> <p>If you know the size of the complete tree (which you can easily store and maintain with the root pointer), you can at least determine which index the median item should be at both before and after the insert.</p> <p>However, you need to know if the previous median item had it's index shifted up by the insert - if the insert point was before or after the median. Unless the insert point and median happen to be in the same node, that's a problem.</p> <p>Overkill way - augment the B+ tree to support calculating the index of an item and searching for indexes. The trick for that is that each node keeps a total of the number of items in the leaf nodes of its subtree. That can be pushed up a level so each branch node has an array of subtree sizes along with its array of child node pointers.</p> <p>This offers two solutions. You could use the information to determine the index for the insert point as you search, or (providing nodes have parent pointers) you could use it to re-determine the index of the previous median item after the insert.</p> <p>[Actually three. After inserting, you could just search for the new half-way index based on the new size without reference to the previous median link.]</p> <p>In terms of data stored for augmentation, though, this turns out to be overkill. You don't need to know the index of the insert point or the previous median - you can make do with knowing which side of the median the insert occurred on. If you know the trail to follow from the root to the median item, you should be able to keep track of which side of it you are as you search for the insert point. So you only need to augment with enough information to find and maintain that trail.</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