Please refer the link https://gateoverflow.in/163103/b-tree-with-sparse-dense-indexing?show=163103#q163103

2 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?

2

7 votes

Best answer

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.

0

Why'd you take floor why not ceil because sir here it's asked about nodes when one node we can store 7 keys and 1428*7 = 9996 not 10000 so 4 keys we missed so it should be ceil isn't it ?

0

yes it should be ceil not floor

ceil(1000/7)=1429

till 1428th node all the nodes will be filled. now minimum occupancy at leaf is ceil(p/2)-1=7

the 9996 keys are already distributed leaving 4 keys left which will be in 1429th node

4<7

so keys will be re-distributed b/w 1428th and 1429th node

ceil(1000/7)=1429

till 1428th node all the nodes will be filled. now minimum occupancy at leaf is ceil(p/2)-1=7

the 9996 keys are already distributed leaving 4 keys left which will be in 1429th node

4<7

so keys will be re-distributed b/w 1428th and 1429th node

1

**The answer is Correct. **

1428*7 = 9996 not 10000 so 4 keys we missed so it should be ceil isn't it ?

These 4 keys will be put in some of those 1428 Index blocks. You can't make new separate Index block for them because it'd violate the minimum occupancy criteria.

so keys will be re-distributed b/w 1428th and 1429th node

Say it were correct. Now you have 7 keys in 1428th node and 4 keys in 1429th node. Now you are saying that we re-distribute these 11 keys in these two nodes without violating the minimum occupancy criteria.. I don't see that possible.

0

ah! got it now.... 11 keys cannot be re-distributed among two nodes such that both nodes will have min 7 keys

yes you're correct @Deepakk Poonia (Dee)

0

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

this formula isnot for order of leaf nodes of B+ tree

right??

0

Moreover in nptel min no of keys is $\left \lceil \frac{p}{2} \right \rceil$

https://nptel.ac.in/courses/106106095/pdf/5_Data_Storage_and_Indexing.pdf

and even wiki too https://en.wikipedia.org/wiki/B%2B_tree

maximum index blocks

means max nodes, right??

0

Another doubt from wiki

Is branching factor and order means same for $B+$ tree??

Then max no. of keys will be $(p-1)$ and min be $\left \lceil \frac{p}{2} \right \rceil$

right??

Is branching factor and order means same for $B+$ tree??

Then max no. of keys will be $(p-1)$ and min be $\left \lceil \frac{p}{2} \right \rceil$

right??

0

for B+ Tree

order of leaves=max number of keys

order of internal nodes=max number of block pointers or what you call branching factor

for both internal and leaf nodes, max number of keys is p-1 and minimum number of keys=$\left \lceil \frac{p}{2} \right \rceil-1$

p is the overall order of tree

see this text from Korth

0

U have written wrong formula for leaf

It should be p(k+r)+b<=block size

And this formula should be used in this question

right??

because, first of all we need order of leaf level node.

0

@srestha

that is the correct formula

p is the max order of a B+ tree

the leaf nodes will have max p-1 keys and thus p-1 record pointers

according to your formula, a leaf of B+ tree will have p keys and p record pointers which is incorrect

0

Donot use any wrong formula

Otherwise, u will get -ve marks in GATE for sure.

Because in that exam 0.00xx matters

0

https://gateoverflow.in/35594/b-tree-find-order

https://gateoverflow.in/3605/gate2006-it-61#viewbutton,

see this

in any solution you'll find these formulas are used

for leaf: (p-1)(k+r)+b<=block size

for internal nodes: (p-1)k+p*b<=block size

0

@srestha

ok assume your formula is correct

It should be p(k+r)+b<=block size

now a leaf node can have max p-1 key pointers. correct?

here p is the max order of the B+ tree

but according to your formula the leaf can have max p key pointers

use the formula and try to draw the leaf node

you'll understand

0

In B+ tree in it's leaf node, there should be p key pointers

Because it has totally different representation from other node

It would be like this

$\left \langle \left \langle K_{1},R_{1} \right \rangle,\left \langle K^{2},R_{2} \right \rangle,\left \langle K_{3},R_{3} \right \rangle,.......{\color{Red} {R_{next}}} \right \rangle$

where $R_{1},R_{2},......$ are key pointers

and $R_{next}$ is block pointer.

So, for eack block size, the size of $p$ key pointer and 1 block pointer should be included in it

Because it has totally different representation from other node

It would be like this

$\left \langle \left \langle K_{1},R_{1} \right \rangle,\left \langle K^{2},R_{2} \right \rangle,\left \langle K_{3},R_{3} \right \rangle,.......{\color{Red} {R_{next}}} \right \rangle$

where $R_{1},R_{2},......$ are key pointers

and $R_{next}$ is block pointer.

So, for eack block size, the size of $p$ key pointer and 1 block pointer should be included in it

0

here p is order of leaf only. overall order of tree will be p+1

because that one block pointer is not counted but all block pointers of internal nodes are counted

order of B+ Tree leaf is max number of keys and order of internal nodes is max number of block pointers

**if the order of B+ Tree is p** then formula is (p-1)(k+r)+b<=block size

0

No, there order of leaf is $p$ and overall order also be $p. $ Because block pointer is not used to count order in $B+$ tree leaf nodes. Only record pointer count it

0

@srestha

https://gateoverflow.in/163103/b-tree-with-sparse-dense-indexing

see this solution

formula for leaf is given

if order of B+ Tree is p

then leaf node will have p-1 keys not p keys

0

@srestha

in that question n is the max no. of keys in the leaf

lets say all nodes are completely filled in all levels

if order of B+ tree is p then all internal nodes will have p-1 keys... right? and all internal nodes will have p block pointers

in case of leaves it'll also have p-1 keys(which happens to be the order of leaf)

now leaf also has p pointers but one of them points to the right sibling that is why it is not counted

[there are p-1 record pointers in leaves and 1 block pointer]

P.S. leaves don't have block pointer(that one 1 block pointer to right sibling is not counted]. leaves have record pointers

I may be wrong. then pls provide me some authentic resource for the formula