Assume one file has r =106 records. Each record takes R = 100 bytes, of which 10

Question

Assume one file has r =106 records. Each record takes R = 100 bytes, of which 10 bytes are for the key of the record. Suppose the key values range from 1 through 1,000,000, inclusive. Assume the block size B is 1000 bytes for all files, and that an address (block pointer, tree node pointer, or data record pointer) takes 10 bytes.

2.    Single Level Index: (15 points)

      e.    What is the blocking factor bfri for the index?

      f.    How many index blocks bi are needed to build the single level primary index?

      g.    How many block accesses on the average are needed to fetch a record by using single level primary index and by doing linear search?

      h.   What is the least number of block accesses to fetch a record by usingsingle level primary index?

Explanation / Answer

order file records r = 106
Record R = 100 bytes
Block size B = 1000 bytes

-----
e)

Bfr = B/R = 1024/100 = 10 records per block

-----------------------
f)
Number of index blocks needed are:
b= r/bfr = 106/10 =~~ 11 blocks

--------------
g)

for linear search....complexity is log2 n ---- block accesses on the average are needed to
fetch a record by using single level primary index and by doing linear search are
log2 b = log2 106 ==> 6.727920454563199 ~~ 7 block accesses.
----------------------------------

h)

minimum Number of index blocks needed are:
b= r/bfr = 106/10 =~~ 10 blocks

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.