D64 Assignment #3

Due Wednesday, February 9, 2000 at 4:00pm.

The assignment should be turned in before class on Wednesday.

Problem Set

1. (30 pts.) Exercise 4.2.6, parts b and c.
2. (30 pts.) Exercise 4.3.1, parts b and c.
3. (10 pts.) Consider a B+ tree (with n = 3) that is initially empty.
   1. You insert the key 14 (and the dbptr for the corresponding record) into the tree.  Show what the tree looks like at this point.
   2. You insert the keys 13,12,11 and 10 (in this order) into the tree.  Show what the tree looks like at this point.
   3. You insert the keys 9,8,7,6,5,4,3,2 and 1 (in this order) into the tree.  Show what the tree looks like at this point.
4. (30 pts.) Consider Consider a sorted file consisting of 1,000,000 contiguous blocks (4kb each). Each block contains 12 fixed size records.  For the following questions, you may assume that:
   • block pointers are 10 bytes
   • record pointers are 11 bytes (10 bytes for the block pointer, 1 byte for the slot number)
   • all attributes are 5 bytes
   Answer the following questions, showing your work if you want any partial credit. State your assumptions clearly.
   1. How many blocks would an extensible hash index require?  Include the size of the directory in your answer.  Assume that the hash function distributes key values uniformly across all of the buckets.  How many accesses are require to find a record given its key?
   2. How many blocks would a linear hash index require?  Assume that the hash function distributes key values uniformly across all of the buckets and that splitting is triggered by an average occupancy above 80%.  How many accesses are required to find a record given its key?