edited by
7,339 views
29 votes
29 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.

edited by

1 Answer

Best answer
37 votes
37 votes

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

Related questions

5 votes
5 votes
5 answers
1
gatecse asked May 2, 2021
3,432 views
For a $B^+$ - tree of order $d$ with $n$ leaf nodes, the number of nodes accessed during a search is $O(\_)$.
26 votes
26 votes
5 answers
3
Kathleen asked Oct 5, 2014
6,876 views
Give a relational algebra expression using only the minimum number of operators from $(∪, −)$ which is equivalent to $R$ $∩$ $S.$
26 votes
26 votes
5 answers
4
Kathleen asked Oct 5, 2014
7,570 views
State True or False with reasonLogical data independence is easier to achieve than physical data independence.