in Databases edited by
6,321 views
27 votes
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 Databases edited by
6.3k views

3 Comments

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

0
0
1
1

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

 

1
1

1 Answer

34 votes
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. 

selected by

3 Comments

how 2d=4 here?
2
2
edited by
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
1
1
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
0
0

Related questions