CSE3330/5330 Homework #4
Due on Thursday April 15, before midnight
Worth 3.33% of the final grade


  1. (40 points) The following B+-tree has leaves consisting of the 8 blocks shown. Assume that no more than 4 keys can be held in a block.
    1. The keys in the index nodes are missing. Fill them in.
    2. Show the tree after insertion of 5.

    hw4.gif

  2. (60 points total) Suppose we have a file of 100,000 records, each record has 200 bytes. Suppose disk blocks are 2048 bytes long. Suppose block addresses are 5 bytes long (i.e., to specify address to a block requires 5 bytes) and also pointers to records are 5 bytes long (i.e., a pointer that specifies the address of a record in a block needs 5 bytes). Determine the number of disk accesses to do a successful lookup for a record for each of the cases below. Also determine, when possible, the amount of disk space you need to store the index structures or hash structure, or any other structure used in the cases below. Explain your answers.
    1. (10 points) The file is stored as a heap file (in an unspanned organization).
    2. (15 points) Hashing is used with 1000 buckets and the file itself is stored as a heap file.
    3. (15 points) Primary indexing is used and the file is ordered. A search key field requires 15 bytes.
    4. (20 points) Secondary indexing is used using a B+-tree structure. Here too, a search key field requires 15 bytes. Assume a tree pointer also requires 5 bytes. Consider the worst case.

Submit Homework #4:

Last modified: 04/08/10 by Leonidas Fegaras