CIS 430 - Advanced Database Topics | Assignment 1 | Complete Solution

Do the following questions:

1. (10 marks)  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.)

1. (5 marks)  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.

1. (5 marks)  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.

1. (10 marks)  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.