file structure and indexing

Question

DB file consist 1250 records.Block can hold either 3 records or(10 keys,11 pointers)

How many min index blocks and min level of index required for sparse B+ tree Index for this DB.

Answer 1

ceil(1250/3)=417 blocks are required

so for each block one 417 pointers are required so number of blocks is ceil(417/11)=38  ---------1st level

again these 38 blocks are to be indexed so 38 pointers so number of blocks is ceil(38/11)=4-----2nd level

again 4 pointers so ceil(4/11)=1-----3rd level

min index blocks=38+4+1=43

min levels are 3

Comments

For the first level index records  it must be 417/10  ? (for the leaf property)

---

Why did we not consider the no of leaf nodes at the 1st level? Shouldn't it be 417/10?

---

level 2,3 are index records and level 1 contains data records.

Answer 2

root                 min  max

Block pointer   2       11

keys                1       10

----------------------------------------------

non root           min   max

block pointer     6        11

keys                5         10

-----------------------------------------------

levels    #of nodes      #of B.p            #of keys

1            1                  2                        1

2            2                2*6                     2*5

3             12              12*6                   12*5

4              72             72*6                    72*5

5              432           432*6                  432*5(2160)

in B+tree total no of nodes =no of leaf nodes

given no of records is 1252<2160

so no of levels required is 5.

each block can hold 3 records so total no of block=1250/3

                                                                           =417

Comments

Leaf Node is not satisfying the B+ tree "storage of minimum record" property. If the level is 5. **Assuming that the order of the leaf node is 11 which is same as internal node.

Answer 3

Ans will be 4 bcaz

1250/3= 417 blocks

1st level 417/5= 83

2nd laval 83/6 =13

3rd 13/6=2

block at 4 th level =1

Comments

@Anupam This is the answer for maximum levels and not minimum levels.