Why use Multilevel index?
In ordered sequential file number of block access required is log(2,b) where b is number of blocks to store the index file. Multilevel index were introduced to reduce the number of block access to access the record
Number of block access required for multilevel index is log(bfr,b)
so number of access are less if bfr is greater than 2 for multilevel index than for ordered index file
Blocking factor
blocking factor or fan out of multilevel index specifies number of records that can be accumulated in single block or records per block
Problem 1.1
Consider ordered data file with following parametersr (number of records) = 16348
R (record size) = 32 bytes
B (block size) = 1024 bytes
index stored as key + pointer pair
key value = 10 bytes
block pointer = 6 bytes
Find the number of first level and second level blocks required for multilevel index on this
Solution:
Number of First level Blocks
Lets find Number of blocks in data file
Number of records that can be accumulated in block i.e
Blocking factor bfr = 1024/32 = 2^5
so, can have 32 records in a block
now how many such blocks are required for 16348 records
number of blocks required for data file = (r/bfr)
= 16348/ 32 ~= 511
now we know we need 511 entries in the first level index
primary level of multilevel index and data file |
i.e how many blocks in first level of multilevel index will be required to store this much entries where each entry is of 16 bytes(key + pointer size)
R' = 16
B = 1024
bfr' = 1024/16 = 2^6
Blocking factor or fan-out for first level and its subsequent levels will be same because index entry is of same size
so number of blocks required for 512 entries would be = r'/bfr'
= 511/64 = 2^3 ~= 8
secondary level index |
Number of Second level Blocks
Its clear that only a single second level block would be required to store 8 entries
but lets calculate
Number of entries in second level = Number of blocks in the first level = 8
Number of blocks in second level = (number of fist level blocks)/(bfr)
= r''/bfr'
blocking factor bfr' is same here as second level because here also we will be storing key + pointer pair
Number of records are now 8.
So, Number of blocks for second level = 8/64 ~= 1
Problem 1.2
For secondary index on unordered key data file
with same parameters
Solution:
In case of secondary index there is one index entry required for each data record in data file
Number of First level blocks
First level index will store index entries for all the records(16348) in data file
Number of blocks needed for first level index = r/bfr = 16348 / 64 ~= 256
(bfr = 1024/(10+6) )
Number of entries in second level = Number of blocks in first level = 256
bfr = 64 is same and r = 256
so Number of second level blocks = 256/64 = 4
No comments:
Post a Comment