2
$\begingroup$

I was reading about B+ tree insertion. The algorithm takes following form:

  1. Insert the new node as the leaf node.

  2. If the leaf node overflows, split the node and copy the middle element to the parent index node.

  3. If the index node overflows, split that node and move the middle element to the parent index node.

However, adding the new index value in the parent node may cause it, in turn, to split. In fact, all the nodes on the path from a leaf to the root may split when a new value is added to a leaf node. If the root node splits, the tree grows by one level.

Now the book asks to insert 33 in following tree of order 4:

enter image description here

I was guessing how those [10,20,30] occur to be the root node. Before performing first split while forming above tree, these [10.20,30] should be in some leaf and in any case they should be present in some leaf.

In other words I feel that all internal node keys should also be present in the leaves. However thats not the case with [10,20,30]. This is also inline with the fact that in B+ tree all data is present in the leaves, so all keys should be present in the leaves.

Another example on youtube also have 13 and 30 in the root node but not in any leaf.

Am I wrong with the fact that all internal node keys should also be in the leaves?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

The internal keys come from values also stored in leaves, but if you allow deletions, the value could be deleted from the leaf after it is created and used in the internal node. Deleting the value from a leaf won't change any internal nodes, unless the leaf becomes underfilled. With the insertion you list, it would have the property you are thinking of if there were no deletions.

On the other hand, it is possible that the author wasn't thinking of either the property you name, nor the possibility of deletions, when making the question, and just used 10, 20, 30 as easy separators. For sure, I have written questions with mistakes before, and usually, even with a mistake in the question, it can usually be answered properly to see if the student understands the material (insertion in this case). If a student then asked me what your post asks? I would be pleased with their understanding of the material to notice this property.

Improve this answer
$\endgroup$
3
  • $\begingroup$ So the question is not incorrect and to get this state of a B+ tree, some deletions should have occurred earlier right? $\endgroup$
    – Mahesha999
    Sep 4, 2016 at 9:23
  • 1
    $\begingroup$ The question doesn't specify where the tree came from. It could have been created by some sequence of insertions and deletions, but not by a set of only insertions. $\endgroup$
    – Algorithms with Attitude
    Sep 9, 2016 at 4:01
  • $\begingroup$ yeah I was not talking about specific tree, I wanted to know when such tree can occur in general. You were very right with "It could have been created by some sequence of insertions and deletions, but not by a set of only insertions" $\endgroup$
    – Mahesha999
    Sep 9, 2016 at 7:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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