edited by
15,963 views
46 votes
46 votes

Consider the $B^+$ tree in the adjoining figure, where each node has at most two keys and three links.

Keys $K15$ and then $K25$ are inserted into this tree in that order. Exactly how many of the following nodes (disregarding the links) will be present in the tree after the two insertions?

  1. $1$
  2. $2$
  3. $3$
  4. $4$
edited by

5 Answers

Best answer
61 votes
61 votes

Option (A) is correct.

It is a $B^+$ Tree.

After inserting $K15$ we get

 

Now, we insert $K25$, which gives -

So, we see in the final tree only $\text{(K20, K25)}$ is present. Hence, 1 (Ans).

edited by
12 votes
12 votes
Answer: A

Only one node will be there, i.e. (K 20,K 25). After inserting K 15, the node (K 10, K 20) splits and K 15 moves up to form (K 15,K 30).

After K 25 is inserted, K20 moves up to the root  & splits up (K15,K30) &  it forms (K 20,K 25).

So, after final insertion only (K20,K25) present.  So, 1 is the answer.
1 votes
1 votes
I am not adding complete answer but just adding some useful points

In B+ tree unlike B tree in case of overflow we keep value in leaf as well as promote value to parent node

For intermediate nodes operation is same for both B and B++ i..e promote value to parent node don't keep value in child node

In case of left Biasing : when in case of overflow no of keys are odd , take middle key with left sibling

In case of right Biasing : when in case of overflow no of keys are odd , take middle key with right sibling

follow only one biasing for all splits in tree , dont change method in between.  hence answer is (20,25) in either left biasing or right one.
0 votes
0 votes
Caption

[K20,K25] present. Therefore, option A.

 

Answer:

Related questions

53 votes
53 votes
5 answers
4
Ishrat Jahan asked Oct 30, 2014
17,687 views
Consider the following two transactions$: T1$ and $T2.$$\begin{array}{clcl} T1: & \text{read (A);} & T2: & \text{read (B);} \\ & \text{read (B);} & & \text{read (A);} \\ ...