Understand Multilevel Archives - Leon's Blog

I got the following lecture notes from http://computersciencecafe.blogspot.co.uk/2010/10/blocking-factor-in-multilevel-index.html

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 recordNumber 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 fileBlocking factor

bfr = B/R = (block size / record size)
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 parameters

r (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

Find 511 entries can be stored in how many blocks
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

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 second level blocks

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