CSE3330/5330 Homework #4
Due on Thursday April 15, before midnight
Worth 3.33% of the final grade
- (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.
- The keys in the index nodes are missing. Fill them in.
- Show the tree after insertion of 5.
- (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.
- (10 points) The file is stored as a heap file (in an unspanned organization).
- (15 points) Hashing is used with 1000 buckets and the file itself is stored as a heap file.
- (15 points) Primary indexing is used and the file is ordered.
A search key field requires 15 bytes.
- (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.
Last modified: 04/08/10 by Leonidas Fegaras