Indexing Assignment #4 Solution

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.

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.

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.

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 incremen- tally and draw the final table;  that  is, insert  one at  a time, check the condition,  and move to the next one.