Consider the B+ Tree, illustrated below, it has a maximum number of 2 split values per interior node, and 2 key values in its leaf nodes.

Question

B+ Trees question

A) Fill in the 4 missing values above. (BTW: one of the empty boxes has more than one correct answer)

B) Given the following B+ tree, (same number of keys, etc. as above)

B+ Tree question 2

Draw the tree as it would appear after an additional row with key-value 6 inserted.

 

Summary

In question-A, the maximum number of keys that can be present per node in the case of both internal node and leaf is 2.
The B+ tree has the following set of nodes.
{1, 3, 3, 5, 5, 5, 18, 23, 23, 24, 24, 26, 26, 31, 65, 65, 96}
The missing values are shown.
In the second question, the B+ tree is provided with the set of nodes {2, 5, 5, 7}. To this tree, another key 6 is inserted as shown below under explanation.
In this question also, the maximum keys that can be a present per node in the case of both internal node and leaf are 2.

 

Explanation

(A.) Here, there are no empty blanks provided to insert the missing values.
But it is given that there can be a maximum of 2 keys in both the internal nodes and leaves.
Hence, we are going to give values that can be inserted in the tree so that all nodes will have 2 keys at least.
⦁ The leaf node with the key 0001.
Here, there is a vacancy for one more node.
It can be either 0001 or 0002, as the number can be greater than or equal to 1 and should be less than 3.

⦁ The leaf node with the key 0023.
Here also there is a vacancy for one more node.
It can be either 0023, as the number should be less than 24 and greater than or equal to 23.

⦁ The leaf node with the key 0024.
Here also there is a vacancy for one more node.
It can be either 0024 or 0025, as the number should be greater than or equal to 24 and less than 26.

⦁ The internal node with the key 0065.
Here also there is a vacancy for one more node.
It can be any number in the range from 31 to 65.

(A.) Given B+ tree is: 

b+ tree diagram

The first steps are provided to insert the given B+ tree: 

    • Insert 5: 

1st step

    • Insert 2:

2nd step

    • Insert 5:

third step

    • Insert 7

4th step

    • Insert 6

5th step

 

 

Also read, ARRAY OF STRUCTURES IN C

Share this post

Leave a Reply

Your email address will not be published. Required fields are marked *