E xercise 14.1.5: Suppose th at blocks can hold either three records, ten keypoi
ID: 665829 • Letter: E
Question
E xercise 14.1.5: Suppose th at blocks can hold either three records, ten keypointer
pairs, or fifty pointers. Using the indirect-buckets scheme of Fig. shown below:
a) If the average search-key value appears in 10 records, how many blocks
do we need to hold 3000 records and its secondary index structure? How
many blocks would be needed if we did not use buckets?
! b) If there are no constraints on the number of records that can have a given
search-key value, what are the minimum and maximum number of blocks
needed?
Explanation / Answer
a) If the average search-key value appears in 10 records, how many blocks do we need to hold 3000 records and its secondary index structure? How many blocks would be needed if we did not use buckets?
We need 3000/3=1000 data blocks. If we use buckets, we need key-pointer pair for only 3000/10=300 different keys which can fit on 30 index blocks. We also need 3000 pointers in the buckets, which would fit in 60 blocks. Totally, we need 1000+30+60=1090 blocks in total. If we do not use bucket, we need the same 1000 data blocks. However, we need a key pointer pair for each of the 3000 records, which would fit on 300 blocks. Thus totally, we need 1000+300=1300 blocks.
b) If there are no constraints on the number of records that can have a given search-key value, what are the minimum and maximum number of blocks needed?
For the maximum situation, we still need 3000/3=1000 data blocks. However, each search-key value appears only in 1 record. We need key-pointer pair for only 3000 different keys that fit on 300 index blocks. We also need 3000 pointers in the buckets, which would fit in 60 blocks. Thus we need 1000+300+60=1360 blocks in total. For the minimum situation, each search-key value appears in 3000 records. Thus we need key-pointer pair for only 1 key that fit on 1 index block. We also need 3000 pointers in the buckets, which would fit in 60 blocks. Thus we need 1000+1+60=1061 blocks in total.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.