Cnstruct anbspb-treenbspwithnbspnnbsp 3 maximum three

Question

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

Search key value	Hash value
Bob	3
Dan	1
Stephan	5
Sandi	9
Edward	5
Leon	0
Paul	8
Gabriel	7

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.

Search Key Value	Hash value
Chapman	10011100
Cleese	11010011
Connolly	00111000
Gilliam	11111010
Idle	10110110
Jones	01000111
Milligan	00011001
Palin	10100111

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.

Answer 1

The following assignments are related to constructing a B+ tree having nodes. You have to perform the tasks as according to the guidance, illustrated below: Q1. Create a B+-tree having n = 3 (utmost three pointers per node), by using the method outlined in course notes, having the following items, entered to the tree in the given manner: 53, 17, 47, 21, 19, 32, 5, 39, 8, 24 a) Illustrate the steps in constructing your tree, having a sketch for every time a new node is added. b) If you have to split a node as an odd number of items, place the bigger quantity in the left new node and the remainder in the right. Q2. Determine the maximum height of a B+-tree having n = 7 be if it contained 53,842,936,361 items? If you do not encompass a calculator having a log10 button, use windows calculator.