5,333 views
4 votes
4 votes

Database file consist 50000 records with record size 100 bytes, block size 512 bytes. If sparse B+ tree index build over given database file with search key size 20 bytes both block pointer and record pointer sizes 12 bytes each. How many maximum index blocks required if node order P is defined as between ⎡P/2⎤ to P pointers per node?

1 Answer

Best answer
13 votes
13 votes

Record Size = 100 B
Block Size = 512 B

Hence, We can say, $\left \lfloor \frac{512}{100} \right \rfloor$ = $5$ records per block (Unspanned organisation assumed by default)

So, Number of block required for Database table = $\left \lceil \frac{50000}{5} \right \rceil = 10,000$ Blocks

Now, Let's find the Order $P$ of B+ tree.

Search Key size = 20 B
Pointer size = 12 B
And Order is defined as usual convention.

So, $(P-1)20 B + (P \times 12 B) \leq 512B$

Hence, $P = 16$

So, In any node of B+ tree, Minimum $\left \lceil \frac{P}{2} \right \rceil -1 = 7$ Keys should present.

Since, We are asked to make the Maximum index blocks in the B+ tree index, So, for that, We will try to fill each Index block as less as possible. Hence, We will try to put only $7$ keys per block.

Here, For B+ trees we can apply Bulk-loading concept. Since there are 10,000 blocks in the database relation.... For Sparse B+ tree index, We need to store 10,000 keys in the Index. 

So, At the Bottom level (I am naming  it 1st level)  of Index, Putting 7 keys per node.. We need $\left \lfloor \frac{10000}{7} \right \rfloor = 1428$ Nodes.

Now, at next upper level (2nd level), We need $1428$ Node Pointers. And Since, We can put minimum 8 pointers per node, We would need $\left \lfloor \frac{1428}{8} \right \rfloor = 178$ Nodes

So, Now, at next upper level (3rd level), We need 178 Node pointers. Hence, $\left \lfloor \frac{178}{8} \right \rfloor = 22$ Nodes.

Going on same way, On next upper level (4th level), We need 22 Node pointers. Hence, $\left \lfloor \frac{22}{8} \right \rfloor = 2$ Nodes.

And finally, at the root level, We can have 2 Node pointers, Hence, 1 Block.

So, Maximum number of Index Blocks required = $1428 + 178 + 22 + 2 + 1 = 1631$ Blocks.

selected by

Related questions

0 votes
0 votes
0 answers
1
2 votes
2 votes
1 answer
3
3 votes
3 votes
1 answer
4
Na462 asked Jan 26, 2019
1,814 views