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.

3.    Multilevel Index: (15 points)

      i.     What is the fan-out value if multi-level index is used?

      j.     How many levels are there so that top level index fits on a single block in multilevel index?

      k.    How many block accesses are needed to fetch a record by using multilevel index?

      l.     What is the key value of the 4th index record on the top level, assuming each index record points to the record with the highest key value in a block of the next level down?

Explanation / Answer

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

--------------------------------------------------
i)

the value for the bfr for the index is used called fan-out
fan-out = B/R = 1000/100 = 10 records per block

-----------------------------------------------------
j) levels for the top level index are : n/fo ^ t
t = round(logfo n)
so fo is fan-out ..which is 10
round( log10 106 ) == > round(2.02) == 2
so...106 / 10x2 ==>106 / 20 == 5 levels.

--------------------------------------------------
k)
block accesses are needed to fetch a record by using multilevel index are log2 n ===> log2 106 ==> 6.727920454563199 ~~ 7 block accesses.

--------------------------------------------------
l) At fifth level
t = round(logfo n) ==> round(log10 4) == 2

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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