Question

Database Management Systems
IT344 -Fundamentals Of Database Systems book
Please Use your own words .
sorry No handwriting
no copy paste

Construct a B+ tree for the following set of key values under the assumption that the number of key values that fit in a node is 3.

Key values (3,10,12,14,29,38,45,55,60,68,11,30)

Show the step involved in inserting each key value.

thank you for your time and effort

Answer 1

B+ trees order:-

For non-leaf:Maximum no.of children it can contain i.e.,Max no.of pointers.

For leaf:- Maximum no.of key value pairs present in a leaf.

B+ Tree insertion:-

overflow:- when no.of search key values exceeds p-1 where p is the order given.(for both leaf and non-leaf).

when overflow occurs:-

For leaf node:-

1.split the node in to 2 nodes such that first node contains floor{(p-1)/2} values and second node contains remaining values.

2.copy the smallest search key value of the second node to the parent node.

For non leaf node:-

1.Split the node in to two nodes such that first node contains floor(p/2)-1 keys.

2.Move the smallest key of the remaining keys to the parent and the second node contains the remaining keys.

solution:-

In the given question,given that the order can be 3.There is no specific order for leaf and non-leaf is given.So I am taking p(leaf)=3 and p(non-leaf)=3.

Overflow occurs when node at leaf or non-leaf exceeds p-1=3-1=2 keys and when overflow occurs

For leaf node:- one node will contain 1 key (since floor[(3-1)/2]=1) and the remaining keys will be placed in the second node and smallest key of second node is pushed to parent node.

For non-leaf node:-one node will contain 1 key(since floor(3/2)-1=1) and the smallest key among the remaining will be pushed to parent and the remaining keys will be placed in the second node.

The correct position of node is finding same as in binary search tree(less than root value-left subtree and greater than root value-Right subtree).