B+tree with sparse/Dense indexing

Question

Database file consists of $10,000$ records with record size of $100$ bytes, block size $512$ bytes. If sparse B+ tree index is built over given database file with search key size $22$ bytes and both block pointer and record pointer of size $12$ bytes each.Find out

a)minimum index block required

b)maximum index block required

my answers a)$143$ b)$325$.

Comments

@joshi_nitish i also have the same concern regarding floor or ceil...

in part b) Max nodes..

2000 block pointers==> 2000/7 =286 index blocks   ( if we take 285 blocks then 285 * 7=1995 pointers .. where will we accommodate the 5 pointers )

Please help.

---

hs_yadav  Ashwin Kulkarni please see if u can help .. read my above comment :)

---

Hi @reena. You're certainly wrong at taking floor. Think like this, you have 2000 boxes. You can hold 14 boxes inside one bigger box. Now how many boxes you need? 2000/14 = 142.87. now for 142 bigger boxes, you have 14 boxes inside each. So 142*14= 1988 boxes are kept inside a bigger box. But what about 12 boxes left? Oh yes! You need 1 more bigger box to keep the last 12 boxes.

Thus you need to take ceil and not floor in this case.

Answer 1

This question needs a bit explanation . Let us solve it systematically .

Firstly this is a B+ tree node ..So leaf index node structure and internal index node structure will differ here.

So talking about leaf node we have  :

                 (p-1) * (record ptr size + key) + block ptr size <= Size of disk block

    ==>       (p-1) * (12 + 22) + 12    <=         512

    ==>       (p-1) * 34                     <=         500

    ==>       p_max  allowable             =           15

  But for leaf node , maximum number of pointers per node   =  15 - 1  =  14

  Order of the B+ tree hence found above     =    15 [This is the maximum possible block pointers for each internal node as well]

  Hence minimum number of pointers in internal node  =  ceil(15 / 2)    =   8

  Accordingly minimum number of record pointers in leaf node   =   8 - 1  =   7 [As number of record ptr = number of keys / node]

  Now we approach the problem in bottom up manner :

 Solution to part a) : 

 Number of records   =   10000

 Block size               =   512 B

 Record size             =   100 B

 Hence number of records per block   =    floor(512 / 100)  =  5

 Hence number of blocks needed to store data    =    10000 / 5    =  2000

 Hence number of pointers needed to point to these data blocks  =   2000 as well as it is sparse indexing .

 Now to find minimum number of index blocks , we need maximum occupancy per block.

 Hence we now start in bottom up manner i.e. starting from leaf level to root as we do for multilevel indexing generally.

 So number of disk block  in leaf level   =  ceil ( Number of pointers in total / Max number of pointers per leaf node )

                      [ Here we take ceil function so as to ensure that some pointers are not lost due to inavailability of disk blocks due to the node size constraint . So truncation is not allowed here and hence we take ceil value ]

                                                         =  ceil ( 2000 / 14 )         =     143

Now as the number of index blocks has not become equal to one , we go to further level of indexing .

Now we have to keep in mind that from this level onwards , we will have 15 instead of 14 as internal node structure has one more pointer to next bottom level as compared to number of record pointers.

Hence number of 2nd level blocks needed               =      ceil( 143 / 15 )     =    10

Thus we go for 1 more level and so number of 3rd level     =     ceil( 10 / 15 )   =   1

Hence minimum number of index blocks needed             =      143  + 10 +  1

                                                                                         =      154

b)  Solution to b) part i.e. maximum number of blocks needed :

Here a bit of modification as compared to the earlier case that for leaf we can have 7 pointers at minimum and 8 in case of an internal node . Also here to take care of minimum occupancy factor , we take floor value to find the number of index nodes at each level because if we take ceil , it is quite possible that one node at that level has a capacity less than minimum occupancy which is undesirable.

Hence number of leaf index nodes     =     floor ( 2000 / 7 )     =     285

          number of 2nd level index nodes i.e. pointing to leaf index nodes  =  floor( 285 / 8 )    =    35

          number of 3rd level index nodes i.e. pointing to leaf index nodes   = floor( 35 / 8 )      =     4

          number of final level index nodes          =   1 [ In final level there has to be 1 node ]

Hence maximum number of index nodes needed     =    285 + 35 + 4 + 1

                                                                                =    325

  

Comments

@aditi19

And I havenot got 

minimum number of pointers in internal node  =  ceil(15 / 2)    =   8

why odrer need to be divide by $2$ when we are finding the pointer in internal node

and in next line why for record pointer -1 is needed??

Accordingly minimum number of record pointers in leaf node   =   8 - 1  =   7 

---

And in these cases , we have no need of maximum
right??

---

@srestha
sorry I'm unable to get your question... could you please mention some more details?