Do the following questions:

1. Construct a B+-tree with n = 3 (maximum three pointers per node), using the method outlined in the course notes, containing the following items, entered into the tree in the following order:

53, 17, 47, 21, 19, 32, 5, 39, 8, 24

• Show the steps in constructing your tree, with a sketch for each time a new node is added.
• When you have to split a node because of an odd number of items, put the larger quantity in the left new node, and the remainder in the right.  (E.g. splitting up 5 items: put 3 in the left, 2 in the right.)

2. What would the maximum height of a B+-tree with n = 7 be if it contained 53,842,936,361 items? If you don't have a calculator with a log₁₀ button, use the Windows calculator and set it to Scientific in the View menu.  Use the formula given on p. 11 of CIS 430 Notes 2.

Show your work to get marks for your answer.

3. Sketch a static hash structure for the following items

Assume that hash values range from 0 to 9.  Show a relation with rows containing the search values, and a hash structure pointing to it.

4. Construct an extendable hash structure for the following data, where the maximum number of entries per bucket is 2.

Enter the items in the order shown here, and sketch the structure each time a new bucket is created.  Use the hash bits progressively from the left side.