now if 34 inserting into tree it voilates property so we have rebalance it

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

4

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

now if 34 inserting into tree it voilates property so we have rebalance it

0

doubts ?

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

2.why always mid term in a block take place in parent block ?

3.how to find diffirence b/w b tree and b+ tree ?

4.in 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

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

2.why always mid term in a block take place in parent block ?

3.how to find diffirence b/w b tree and b+ tree ?

4.in 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

3

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

0

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.

0

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

0

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

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

28 votes

Best answer

7

@sayan

when 34 is inserted the leaf node |32|50|72| will over flow. 50 will go up. and parent node will be

|32|50|81|

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.

when 34 is inserted the leaf node |32|50|72| will over flow. 50 will go up. and parent node will be

|32|50|81|

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.

0

solution depend on what combination one use from <left biasing/right biasing> <left replication/right replication>

0

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.

and if the nodes are full then we will sort the values 32<34<50<72. so isn't it that 32will go upwards.

3

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.

0

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?

0

@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

0

^{+} Tree. So try to find suitable place in the leaf.

2

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.

0

"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 ? .

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

0

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??

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??