treecomputer-sciencedelete-rowb-treetree-balancing

How many keys can be contained at leaf level in B+ Tree


In my database class, my professor was describing about deleting keys from the B+ Tree. If you see the below image:

enter image description here

enter image description here

I totally understood everything except one part where he told that the leaf level nodes can only contain 3 keys at most. As my per my understanding, depending upon the depth of B+ tree, the total keys are decided at the leaf level varies from d to 2*d where d is the depth of tree. Since here d for leaf is 2, why can't the leaf level nodes have 4 keys. Where I am going wrong?

The total number of keys contained at the root level also matter here? Could anyone please explain


Solution

  • I totally understood everything except one part where he told that the leaf level nodes can only contain 3 keys at most.

    If he really said that, he's wrong. It is 4, same as the order of the B+-tree. His own picture proves it: see the bottom right-hand node.

    As my per my understanding, depending upon the depth of B+ tree, the total keys are decided at the leaf level varies from d to 2*d where d is the depth of tree

    Totally wrong. The depth of the tree has nothing to do with it. The number of keys per node is between N/2 and N, except in the root node which can have fewer.