Description
1 Indexing (10 pts)
1. [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?
2. [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.
3
2 B+ tree (30 points)
Consider a B+ tree of degree 2 shown below:
1. [10] Draw the B+ tree that would result from inserting a data entry with key 13.
2. [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.
3. [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.
4
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.
1. [20] Draw the extensible hash table which obeys the above constraints after the four
keys are inserted.
2. [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.
5
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):
1. [10] Insert 1001 and draw the resulting table.
2. [20] With your solution from the previous question, insert 1101, 1110, 0001 incrementally and draw the final table; that is, insert one at a time, check the condition, and
move to the next one.
