Number of blocks at different levels of database indexes

Question

Consider a file of 8192 records. Each record is 16 bytes long and its key field is of size 6 bytes. The file is ordered on a key field, and the file organization is unspanned. The file is stored in a file system with block size 512 bytes, and the size of a block porinte is 10 bytes. If the primary index is built on the key field of the file, and a multivalued index scheme is used to store the primary index, the number of first level and second level blocks in the multilevel index are respectively

a. 8 and 1
b. 16 and 1
c. 8 and 2
d. None of these

Answer 1

As the type of index mentioned is on primary key of the relation , hence the index will come under category of sparse index.As we know in primary index,

No of pointers from 1st level index to data blocks = No of data blocks

as we require only one pointer to each data disk block in case the index is primary and hence ordered index and indexing done on primary key(or) candidate key,else it would be clustering index if it were ordered index on some non key attribute of the relation .

Now , given block size  =  512 bytes

        Record size         =   16 bytes

So , no of records that can be stored in 1 block = 512 / 16

                                                                     = 32

Given total number of records                          = 8192  

So number of data blocks required                   = 8192 / 32

                                                                     = 256

So number of pointers required                        =  256 as mentioned earlier

Now number of <key,pointer> pair that can

be stored in 1 index block                               =  Block size / [Key size + Pointer size]

                                                                    =  512 / [6 + 10]

                                                                    =  32

But we have 256 pointers pointing to records of the database in data blocks

So number of 1st level index blocks required   = Total number of pointers / <Key,pointer> pairs that can be stored in 1 index block

                                                                    = 256 / 32

                                                                    = 8

Now these 8 disk blocks need to be pointed to by higher level of indexing

Now we have found that one index block can store 32 <key,pointer> pairs but here we need only 8.Each pointer of 2nd level index will point to a 1st level index block.

So number of second level index blocks required  = 1

We should remember in questions of multilevel indexing this important fact :

We continue to do indexing to higher levels till number of index blocks at that level = 1

which we have followed here as well.

Hence A) option should be the correct option. 

Comments

great explaination Habib :) . Just give clarification on how the answer will change if we have:

a) Dense index instead of sparse index

b) if we have dense index on key field and then in another part of question on non key field then how answer will change?