B+ and Hashtable Homework#
Question 1: Assume that we are constructing a B+ Tree where page size allows an interior node to have a maximum of 2 keys (3 child pointers), and a leaf can hold a maximum of 3 key-value pairs. Draw the tree after adding the following keys in the following order: 10, 20, 5, 30, 40, 15, 1, 45, 35, 32
Question 2: Let’s imagine a more realistic B+ tree where data is stored in disk blocks (pages) of 8192 bytes (8 KB).
An interior node stores keys and child pointers. A key is 8 bytes and a child pointer is 8 bytes.
A leaf node stores key-value pairs and a pointer to its next sibling. A key is 8 bytes, a value (or a pointer to the value) is 56 bytes, and the sibling pointer is 8 bytes.
a) What is the maximum number of children (the branching factor, \(M\)) an interior node can have? (Remember, an interior node with \(M\) children has \(M-1\) keys).
b) What is the maximum number of key-value pairs (\(L\)) a leaf node can hold? (Remember, a leaf node has \(L\) pairs and one 8-byte sibling pointer).
c) Using your branching factor \(M\) from part (a), what is the maximum number of disk accesses required to find a key in this B+ tree if it stores 1,000,000,000 (one billion) key-value pairs? Assume the root node is not in memory and must be read from disk.
Question 3: Assume an empty hash table with an array size of 7. Use the
hash function h(key)=abs(key)%7. Insert the following keys in this order:
15, 23, 8, 6, 31, 13. Do not resize the array in this problem.
a) Draw the final array if the collisions are handled using separate chaining.
b) Draw the final array if the collisions are handled using open addressing with linear probing.
Question 4: For this question, use separate chaining to handle collisions.
Start with a hash table whose array is of capacity 5. Use the hash function
h(key) = abs(key) % capacity. Allow a maximum load factor of 1, and double
the size of the array when resizing.
Insert the following keys in the following order: 7, 11, 2, 18, 27, 25.
Show the state of the hashtable just before resizing, and then once all the values have been inserted.