Question

Consider the “index calculation” problem we have studied in the class (see lecture note), where we have a relation of 8,000,000 tuples. Again, make the following assumptions:

• the size of disk block (also called disk page): it is usually 4K or 8K bytes, to make our calculation easier, we will use 4000 bytes as a block size
• the size of the search key value: say we index the relation by using an attribute that is part of the primary key, and it is 40 byte string
• the size of physical page addresses: this is needed since every node in the tree will store search key values as well as references to disk pages, i.e., the address of the disk page being referenced. For ease of calculation, we use a 10-byte page address
• each swap takes about 10 milliseconds

1. For this relation, calculate how long it will take to find a particular record if we use dense index, as

described by databaseSystems-71-indexing, page 2? [16 points]

2. Consider again the situation in question 1, with the same dense index, but add one extra level of sparse index, as described by databaseSystems-71-indexing, page 5 – 6. Now, how long it will take to find one particular record? [16 points]

Answer 1

No of records = 800000

Disk Block Size = 4000B

Key = 40B

Page address size = 10B

Swap time = 10ms

1)Use Dense Indexing (level 1)

No of entry in index = no of rewards (dense)

No of entries in index table = 800000

size of each entry in index table = key + address size

= 40 + 10 = 50B

Number of blocks to search in index table =

= 22.9315 units = 23 units

2)Using level 2 index table with sparse indexing

no of records in level 1 of index = 800000

size of records in level 1 of index = 50B

no of entries in index which can be stored in 1 block = Block size / record size of level 1 index

= 4000 / 50 = 80

no of blocks needed for level 1 index = 800000 / 80 = 100000

For level2 indexing, 100000 entries are required since number of blocks at level1 are 100000 &

we use sparse index here.

No of blocks to search in level2 = = 16.6 17

Total no of blocks to search = 17+1+1 = 19

Total time = 19*10ms = 190ms.