515 views
In a database file structure, the search key field is 9 bytes long, the block size is 1024 bytes, a record pointer is 7 bytes and a block pointer is 6 bytes. The largest possible order of a leaf node in a B+ tree implementing this file structure is ________.

I am getting 63 as the answer, but in the solution, it's saying 64. Can anyone check?

edited | 515 views
0
You didn't specify the order whether it is maximum possible pointers or maximum keys?
0

You have to use [P-1](K+R) +B<= 1024

0
@Anu007: Please refer this link: the same question was asked here! Kindly let me know if I am missing anything.

https://gateoverflow.in/1261/gate2007-63-isro2016-59
0

in question (in link) The order of a leaf node in a B++ - tree is the maximum number of (value, data record pointer) pairs it can hold.  is given .

By default order is Maximum number of pointer.

+1

@Anu007

u have written wrong formula

P(K+R) +B<= 1024

ans will be 63

0

@Anu007

Okay, thank you. But how to compute order in this link then:

https://gateoverflow.in/1261/gate2007-63-isro2016-59

For leaf nodes, this is the formula we should use?

[P-1](K+R) +B<= 1024

or

[P](K+R) +B<= 1024

It would be great if you can kindly explain! Thanks in advance

@srestha  Can you please help! I am bit confused here. which one is correct? Maybe I can ping you in chat also.

0

yes @ srestha  its 63 (order_of__leaf)*(record pointer+ key)+ block pointer<=Block size should be

0

In link they are Specify order which is not by default i.e. order= max number of key+ recored pointer.

By default in either leaf or Internal order is Max number of a pointer.

Given question :

In a database file structure, the search key field is 9 bytes long, the block size is 1024 bytes, a record pointer is 7 bytes and a block pointer is 6 bytes. The largest possible order of a leaf node in a B+ tree implementing this file structure is ________.

What question you are reffer:

The order of a leaf node in a B+ - tree is the maximum number of (value, data record pointer) pairs it can hold. Given that the block size is 1K bytes, data record pointer is 7 bytes long, the value field is 9 bytes long and a block pointer is 6 bytes long, what is the order of the leaf node?

Both are not same.

0
in case of B+ tree the order is not same ,internal node and leaf have different order .
0
True! Order is not same in case of non-leaf and leaf node for B+ tree,

But if we use this:

[P](K+R) +B<= 1024

I think it's coming as 63 only.
0

who say this statement, the structure is different but where you got to know an order is not same.

And apply formula 1st.

0

@Anu007 In the link https://gateoverflow.in/1261/gate2007-63-isro2016-59 why they have taken 'n' pairs and not 'n-1' only? Won't one of the pointers in every block be a Block Pointer only?

0
yes in case of non leaf the order is : order_of_node*Block_Pointer +(order_of_node-1)*key<=Block size

n*6+(n-1)*9<=1024

(order of non leaf)n=68 and for leaf order=63
0

Vishal without seeing my comment you are asking same question .

In isro question they define order specifically that order is max number of key and record pointer , see question 1st statement, so we have taken k not k-1.

this question and lsro question difference is they specified what they want that is not by default.

0

@Anu007 Yes..I got your point the first time only that they have defined order in a different way and for this question I have also got 64 as the ans. So i have understood the difference. But how the number of pairs is 'n' and not 'n-1'. Consider the image shown in wikipedia link you gave Here n = 4 but but the number of such pairs(which are defined as Order) is still 3. NO??

0

yes, from wiki
necessary portion is
Leaf nodes have no children, but are constrained so that the number of keys must be at least ⌈ b / 2 ⌉ − 1 and at most b − 1 . In the situation where a B+ tree is nearly empty, it only contains one node, which is a leaf node. (The root is also the single leaf, in this case.) This node is permitted to have as little as one key if necessary, and at most b .

0

what is ans given there?

Can u give a screenshot

yes both formula applicable for different purposes

but I have  seen P(K+R) +B<= BS

in almost all GATE question

0
@Anu

can u plz give brief derivation of the formula
0

srestha This is the screenshot. Almost all problems I solve via this P(K+R) +B<= BS only, I am not sure why (P-1)(K+R) +B<= BS is used here. +3 even in Navathe same formula is used and coming out be 63

0
63 is right ans
0

here it is given that we need to find the order for B+ tree leaf node

so for that we need to know the structure of B+ tree leaf node

in B+ tree leaf node, it consists of (key+record pointer) pair and a single block pointer which points to its adjacent node.

hence the formula

0

Order for a node is the maximum number of pointers that the node contains.

Here, in a B+ tree, leaf node has say p pairs of key and data pointers and one block pointer.

p(key + data pointer) + block pointer <= block size

p(9+7) + 6 <= 1024

p<=1018/16=63.xyz

Thus p=63...........Hence Order of leaf node= Number of Pointers( Data + Block)= 63 +1= 64

@srestha  @souravsaha  @mohitbawankar...... I think the answer 64 is correct.

Kindly correct if I am wrong.



Disk Block size = 1024 bytes

Data Record Pointer size, r = 7 bytes
Value size, v = 9 bytes
Disk Block ptr, P = 6 bytes

o(r + v) + p <= 1024
16o <= 1018
o =< 63

So Ans will be 63.

by Active (2.2k points)
it is talking about leaf node just coz they didnt say anything and the value for record pointer is given .

so if u are suppose to consider it for and try to solve it then u will definately get the answer as 64 .
by (237 points)