6,321 views

Consider $B^+$ - tree of order $d$ shown in figure. (A $B^+$ - tree of order $d$ contains between $d$ and $2d$ keys in each node)

Draw the resulting $B^+$ - tree after $100$ is inserted in the figure below.

We can correlate with this question https://gateoverflow.in/8052/gate2015-2-6

In a B+tree when there is an overflow there will be two cases

if order =p then

1. if Leaf node has an overflow  it will split into two nodes and the number of keys in each nod will be the first node will have ceil(p-1/2) nodes and the next node will have the remaining nodes
2. if the overflow is at other nodes then ceil(p/2)-1 will be in the first node and remaining will go into the next node

For the given $B^+$ tree, $d = 2 \implies 2d = 4.$ Also right biasing is followed as $69$ is to the right of $69$ in the parent node.

We’ll insert $100$ in the sorted position among the leaf nodes.

This causes an overflow and so the node will split into $2$ by moving the element at position $\left \lceil \dfrac{2d+1}{2}\right \rceil =\left \lceil \dfrac{5}{2} \right \rceil = 3,$ which is $100.$ Thus we get.

This again causes an overflow at the root node and $69$ needs to be moved up forming a new root. Here, $69$ is not a record pointer (only leaf nodes in $B^+$ tree contains record pointers) and so we need not replicate it while moving up.

Now all the property of $B^+$ tree is satisfied and the insertion algorithm terminates.

by

how 2d=4 here?
edited
here 2d is maximum no of keys.. and in the figure max. keys present is 4.. so 2d=4.. i guess..maybe m sure . :P
yes here the keys are between d and 2d and  that is the maximum number of keys that can be in node =4 here making 2d=4  and the order of the tree is max no of keys in a node+1 = 4+1=5