edited by
8,208 views
33 votes
33 votes

The below figure shows a $B^+$ tree where only key values are indicated in the records. Each block can hold upto three records. A record with a key value $34$ is inserted into the $B^+$ tree. Obtain the modified $B^+$ tree after insertion.

edited by

4 Answers

Best answer
12 votes
12 votes

$B^+$ tree Reference.

In a $B^+$ tree only the leaf nodes have a pointer to actual data (record pointers) whereas internal nodes points to index blocks. 

In the given question we have 

  • $M: \text{Number of pointers in internal nodes} = 3.$
  • $L: \text{Number of data items in a leaf node} = 3.$
  • Further we can see that right biasing is used while splitting a node (same key value moving to the right, in a $B^+$ tree all internal key values will be present in leaf node as only the leaf node actually points to the data record)

To insert $34$ we’ll first place it in the sorted order among the leaf nodes.

Now, we see that the block (being the leaf node the pointers here are record pointers) having $34$ is overflowing and so we’ll split it and move the center element to the parent block. There might be a confusion as to whether $34$ or $50$ should move up, but if we see the question it is following right biasing (same key value is going to the right) and so $50$ must move up. 

Now, we have an overflow in the internal node as the maximum capacity of an internal node is $3$ block pointers but we are having $4$ here. So we must again split and move $50$ upwards.

Now we have an overflow in the root node and so we must again split and move $120$ upwards making a new root.

Now all the $B^+$ tree requirements are satisfied and so the insertion algorithm terminates.

edited by
39 votes
39 votes

First of all, it's not a $B$ Tree given in the question, it's $B+$ Tree.
And, following will be the resulted $B+$ tree after the insertion of $34$:

 

edited by
15 votes
15 votes
B Tree after inserting 34.

                    120

        34                       250

32           81          150,205       520

Related questions

11 votes
11 votes
1 answer
2
makhdoom ghaya asked Nov 30, 2016
7,138 views
For secondary key processing which of the following file organizations is preferred? Give a one line justification:Indexed sequential file organization.Two-way linked lis...
29 votes
29 votes
4 answers
3
makhdoom ghaya asked Dec 15, 2016
5,728 views
Symbolize the expression "Every mother loves her children" in predicate logic.
25 votes
25 votes
4 answers
4
makhdoom ghaya asked Dec 15, 2016
2,762 views
Find the number of single valued functions from set $A$ to another set $B,$ given that the cardinalities of the sets $A$ and $B$ are $m$ and $n$ respectively.