Q.1 [40 pts] Given an extendable hash structure where buckets can hold 3 search key values.
The entries with the key values listed below are inserted in the following order:
3, 151, 71, 29, 25, 92, 111, 16, 22, 138, 43, 95, 13, 41
The hash function given is h(x) = x mod 16. The hash value of a search key is a 4-bit binary value. Use the most significant bit of the hash value during insertion. Suppose that the extendable hash table is initially empty. Show the contents of the hash table and the bucket address table after each of the bucket splits (indicating which insertions lead to bucket splits), and after all the integers are inserted.
Q.2 [32 pts] Construct a B+ tree where n=4 (the maximum number of pointers for each node of the tree is 4), by inserting the entries with the search key values listed below in the following order:
3, 151, 71, 29, 25, 92, 111, 16, 22, 138, 43, 95, 13, 41 Draw the resulting tree.
Q.3 [28 pts, 14 pts each] Consider the following B+ tree. The maximum number of pointers for each node of the tree is 3 (n = 3). The notation k* in a leaf node corresponds to a pair of <p, k>, where k is the search key value and p is the pointer to the file record with the key value k.
(a) Draw the resulting tree after deleting the entries with search key values k = 12, 10, 13, 1, 4, and 11 successively.
(b) Draw the resulting tree after deleting the entries with search key values k = 15, 25, 13, 16, 11, and 9 successively from the original tree.
