We wish to construct a B+ tree with fan-out (the number of pointers per node)…

PYQ GATE 2001Modified — slightly modified from the official paper; see the solution

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.

(a) Show the tree after insertion of 10, after insertion of 30, and after insertion of 90. Intermediate trees need not be shown.

(b) The key values 30 and 10 are now deleted from the tree in that order. Show the tree after each deletion.

Use leaves with one or two keys; on a three-key leaf overflow keep the first two keys in the left leaf and promote the first key of the new right leaf. Internal nodes have two or three children; on deletion borrow from the right sibling when possible, otherwise merge, and update separators to each right subtree’s smallest key.

Attempted by 1 students.

Sign up free to check your answer

Sign up free

Explore the full course: Zero To Hero

Loading lesson…