Description
1 Indexing (10 pts)
- [7] Suppose we want to build an index on a relation R which has a total of x records, with each block capable of holding either y records or z key-pointer pairs. Assuming x is divisible by y, please answer the following questions (if your value evaluates to a fraction, use ceiling or floor as appropriate):
(a) [3] Suppose you construct a simple single level index, and that index is dense. How many index blocks are required to access all of the records of R?
(b) [4] Suppose the index built is sparse. If the index stores a pointer to the lowest search key in each block, and the index is a simple single level index, how many data blocks do we need? How many index blocks do we need?
- [3] True/False question – In order to use a dense index, you will have to have the data file sorted by the search key; otherwise, you will need to use a sparse index. Explain your reasoning.
2 B+ tree (30 points)
Consider a B+ tree of degree 2 shown below:
- [10] Draw the B+ tree that would result from inserting a data entry with key 13.
- [10] Based on the B+ tree that you drew in the previous question, draw the B+ tree that would result from deleting the data entry with key 75.
- [10] Based on the B+ tree that you drew in the previous question, draw the B+ tree that would result from deleting the data entry with key 89.
3 Extensible Hashing (30 pts)
Assume you have a extensible hash table with hash function h(k) = k mod 13, expressed as a binary string of size 4, and data block of size 2 (i.e., it can accommodate two tuples). You are asked to index the following key values in order: 25, 13, 23, 21.
- [20] Draw the extensible hash table which obeys the above constraints after the four keys are inserted.
- [10] Using your solution to the previous question, now consider insertion of keys 18 and 20 into the hash table, and draw the resulting hash table.
4 Linear Hashing (30 pts)
Consider a linear hash table with r ≤ 1.76n with each data block capable of holding 2 records (that is, the average number of record per bucket should not exceed 88% of the total number of records per block):
- [10] Insert 1001 and draw the resulting table.
- [20] With your solution from the previous question, insert 1101, 1110, 0001 incremen- tally and draw the final table; that is, insert one at a time, check the condition, and move to the next one.