MadeEasy Test Series 2018: Databases - Indexing

Question

Database file consist 1250 records. Block can hold either 3 records or (10 keys, 11 pointers). The maximum number of levels of index required for sparse B+ tree index for database file are ______.

Answer 1

NOTE – For maximum number of level or height there will be minimum number of keys in each node which in this case 5 so this makes number of pointers 6

Blocks required = 1250/3 = 417

Level 1 = floor(417/5) = 83

Level 2 = floor(83/6) = 13

Level 3 = floor(13/6) = 2

Level 4 = floor(2/6) = 1

So, total no. of levels = 4

Answer 2

Blocks required = 1250/3 = 417

Level 1 = ceil(417/11) = 38

Level 2 = ceil(38/11) = 4

Level 3 = ceil(4/11) = 1

So, total no. of levels = 3

Minimum index blocks = 38 + 4 + 1 = 43

Comments

if there are $3$ records in each block, then how $10$ keys are in each block??

---

Characteristics of B+ Tree:

1. Data records are stored only in leaves

2. Internal nodes just stores keys

3.  The leaf nodes, form the first level of the index, with the internal nodes forming the other levels of a            multilevel index.

The structure of the internal nodes of a B+ tree of order ‘a’ is as follows:

.

$p_{1}$

$k_{1}$

$p_{2}$

$k_{2}$

...

$p_{n-1}$

$k_{n-1}$

$p_{n}$

 

So, I thought the B+ tree's internal node will be something like this and I am not sure whether the concept is like this:

   

$p_{1}$

$k_{1}$

$p_{2}$

$k_{2}$

.....

$p_{10}$

$k_{10}$

$p_{11}$

 

Please check whether it's right @srestha

---

Why are we not including 10 keys

---

for maximum number of level minimum number of keys in each node.

each node can have 10 keys means minimum number of keys = 5

and therefore  pointer = 6

---

so you mean instead of 11 we will use 6 .

---

yeah there are many question like that you can look at them under the tag indexing

---

I think in minimum level 1 = ceil(417/10)  not this ceil(417/11)

Blocks required = 1250/3 = 417

level 1 = ceil(417/1)

 

Level 2 = ceil(38/11) = 4

Level 3 = ceil(4/11) = 1

So, total no. of levels = 3

Minimum index blocks = 38 + 4 + 1 = 43