711 views

We wish to construct a $B^+$ tree with fan-out (the number of pointers per node) equal to 3 for the following set of key values:

80, 50, 10, 70, 30, 100, 90

Assume that the tree is initially empty and the values are added in the order given.

1. Show the tree after insertion of 10, after insertion of 30, and after insertion of 90. Intermediate trees need not be shown.
2. The key values 30 and 10 are now deleted from the tree in that order show the tree after each deletion.
edited | 711 views
0
fanout means no of records per node but b+ trees contain an additional pointer pointing to next node so in this case would splitting will take place after insertion of 2 key values or 3 key values? Plz explain...
0
After 2 key values. Also, that additional pointer appears only in leaves.
+1
why split after 2 key value ??

since order = 3, so we can have 2 key elements in a node with no problem but when we have 3 key then it should be a overflow right ??
0
plz explain this one....
0
Same like btree

+1 vote

in the B+ tree order of internal node and order of leaf node are different

order of internal node is maximum no of childrens

order of leaf node is maximum no of key value pair in the leaf

in the question it is given that

B+ tree with fan-out (the number of pointers per node) equal to 3

so from this we can easily conclude that the order of internal node is 3

and order of leaf node is 2   ( just think about it why it is 2 ?? you will get the answer )

for internal node

since order = 3, so we can have 2 key elements in a node this is  not problem but when we have 3 key then we have to split them

for leaf node

since order = 2, so we can have 2 key elements in a node with no problem but when we have 3 key then we have to split them ( just think about it why it is 2 ??

it is because given fan-out (the number of pointers per node) equal to 3

one pointer point to next leaf and two pointer point to the record means there are maximum  two record pointer

and order of leaf node is  maximum number of key value pair

so it is 2

0
Few doubts:

1. After inserting 100 and splitting the nodes, the node containing 70,80 is pointing to 2 child nodes. Is it correct. Which  pointer will be NULL?

2. In final tree, Root node is having 2 elements. But in Root node there should be only one element. So to split this node so that root contains one element