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

Dark Mode

27 votes

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.

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

if order =p then

- 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
- 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

1

34 votes

Best answer

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.