1
$\begingroup$

This and several other resources suggest to "Always a node that gets the middle key from bottom splits, should drop one item for a new middle key".

To illustrate with an example.

For 5-way B+-tree,

(24, 25, 44, 79) is one of the leaf nodes with its root being (..,24,80,...)

(..,24,80,...)
      \ 
       \ 
        \
       (24, 25, 44, 79)

After Inserting 40.

The node (24, 25, 40, 44, 79) gets overloaded and is forced to split(considering the siblings are full as well).

In such a case, is there any advantage of splitting it as

(24, 25) (40, 44, 79) over (24, 25, 40) (44, 79)

Is this split A

(..,24, 40, 80,...)           
         | \ 
         |  \ 
         |   \
    (24, 25)  (40,44, 79)

better than this split B?

 (..,24, 44, 80,...)           
          | \ 
          |  \ 
          |   \
 (24, 25, 40)  (44, 79)

If so, what makes A correct and B wrong, considering that both are satisfying the rules of the B+ tree.

I couldn't find any resource to back my argument that B is equally correct as A.

$\endgroup$
1
$\begingroup$

There is no advantage to choosing one over the other.

"Real" B+-tree implementations will often rebalance if they can, rather than splitting. When a node becomes overfull, if there is a sibling (whether to the left or the right) which isn't yet full, it's often better to balance the entries evenly between this node and its sibling. This saves an allocation.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks. My doubt was explicitly when the siblings are full and it needs to split. I haven't found any material to support the claim that split A is better than split B. It made me wonder because almost every implementation and visualization goes with split A. $\endgroup$ – Vamsidhar Dec 3 '19 at 0:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.