The Gateway to Computer Science Excellence
+23 votes

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


in Databases by Boss (30.7k points)
edited by | 2.1k views
Each block can hold upto three records ( 3 pointers) so max keys will be 3-1=2 in all internal nodes
now if 34 inserting into tree it voilates property so we have rebalance it

First of all, this is not a B-Tree in the question, it's B+ Tree.

doubts ?

1.difference b/w record and pointer ?(for above question)

2.why always mid term in a block take place in parent block ? to find diffirence b/w b tree and b+ tree ? the above question 32 present 2 time one is in child and another is in parents so , why both not take place in same level

Each block can hold upto three records

Here "block" refers to both internal block and external block (Leaf) of the B+ tree. Now, internal block can hold upto three records mean that max pointers of an internal block is three. For external block(leaf), it means that <Key, RecordPointer> pairs are three

How 3 keys are possible at leaf nodes? it is given in the question " Each block can hold upto three records."  means 3 max pointers and 2 keys are possible at each node .Please help.

Insertion Takes place only in the leaf node of B+ Tree. So try to find suitable place in the leaf.

Here order of internal node is 3 evident from the diagram (maximum block pointer)

Order for leaf is 4 again from the diagram( order of leaf node is number of key dataptr pairs which is 3 plus one block pointer for pointing to the sibling for range queries hence 4)

Now apply the rules:

Order internal node =3

Leaf node=4

4 Answers

+26 votes
Best answer

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


by Boss (44.1k points)
edited by
Can you please explain the 2nd step where you are merging 50,120,250?

when 34 is inserted the leaf node |32|50|72| will over flow. 50 will go up. and parent node will be
now this internal node is overflow, as you can see in tree, at most 2 keys can be stored.
In second step it has been shown that when 50 moves to its parent node then the root node |50|120|250| will overflow and will split.
Okay thank you for the explanation
When we have an overflow at leaf ... 34 will be going up right ? How you have put 50 will go up ?
solution depend on what combination one use from <left biasing/right biasing>  <left replication/right replication>
what is replication?

and if the nodes are full then we will sort the values 32<34<50<72. so isn't it that 32will go upwards.
34 should come in place of 50,because in either of the case left or right-biased splitting is always done at ceiling-value of s=(p(leaf)+1)/2 and in the leaf-node the records till "s" are retained others are moved to a newly-created leaf-node. So "34" should go up after splitting.
When we insert 34 then the keys will be 32 34 50 72 then why you have considered that 50 will go up and not 34?
@poonam if 34 will go up then 50 woll be in the right side else if 50 will go up 34 will be in left side we can choose both the decision here

Insertion Takes place only in the leaf node of B+ Tree. So try to find suitable place in the leaf.


Each block can hold upto three records

 Agree with the first step. But as each block can contain 3 records, then why 32,50,81 is an overflow? It is not full yet.

order of internal node is 3 which means it can have 3 tree pointers and hence 3-1=2 keys.
"Each block can hold upto three records"

Means In b+ tree record are stored in leaf so they are talking about order of leaf which is 3.then what will be the underflow and overflow condition 1 and 3 ? .
You have used right biasing to split and move the key, right?

what if we do left biasing in which 34 will go up and split node/block accordingly??

is that possible that two different B+ trees are possible if not specifying the biasing??
You should see what biasing is used in question and then apply it. In question right biasing is used.(see the value $150$)

Hmmm, correct.

for visual understanding

+14 votes
B Tree after inserting 34.


        34                       250

32           81          150,205       520
by Active (1.6k points)
+11 votes

Considering it as b+ tree

by Loyal (8k points)
This must be the correct answer
+1 vote

Correct me if u find something wrong

by Boss (11.6k points)
edited by

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,741 questions
57,253 answers
104,699 users