The Gateway to Computer Science Excellence

+2 votes

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?

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

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

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.

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

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

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.

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.

Refere this link https://en.wikipedia.org/wiki/B%2B_tree heading name Characteristics

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

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

@ 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.

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.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,324 answers

198,405 comments

105,169 users