Database indexing

Question

Comments

Block Factor of DB table = 2² 

Formula for Block factor of DB table = $\frac{\text{Block size}}{\text{Size of each record}} = \frac{4KB}{1KB}$

Number of blocks required at DB table level = $\frac{2^{30}}{2^2} = 2^{28}$

Formula for Block factor of Index table = $\frac{\text{Block size}}{\text{Key + Pointer size}}$

Block factor Index table :- $\frac{2^{12}}{2+2} = 2^{10}$

Number of Block required at 1st level index = $\frac{\text{Number of entries}}{\text{Block factor of Index table}} = \frac{2^{28}}{2^{10}} = 2^{18}$

Number of Block required at 2nd level index = $\frac{\text{Number of entries}}{\text{Block factor of Index table}} = \frac{2^{18}}{2^{10}} = 2^{8}$

Number of Block required at 3rd level index = $\frac{\text{Number of entries}}{\text{Block factor of Index table}} = \frac{2^{8}}{2^{10}} = 1$ Because in each case we are taking ceil value.

So, in total it is $2^{18} + 2^8 + 1$ 

Closet option is 2^20.

---

@subhanshu why are you using multi level indexing.

---

Becuase it is mentioned in the question "sparse index".

---

But primary index or cluster index is also sparse then why multilevel used ?

---

@hsd31196 The very first level (which is near to DB table is the sparse index as per question says) and then we used the general implementation.