MadeEasy Test Series 2018: Databases - Indexing

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

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

Comments

You didn't specify the order whether it is maximum possible pointers or maximum keys?

---

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

Answer will be 64 only

---

@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

---

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.

---

@Anu007

u have written wrong formula

P(K+R) +B<= 1024

ans will be 63

---

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

---

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

---

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.

---

in case of B+ tree the order is not same ,internal node and leaf have different order .

---

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.

---

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. 

---

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

---

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

---

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.

---

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

---

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 .

---

@ souravsaha

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

---

@Anu

can u plz give brief derivation of the formula

---

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

---

even in Navathe same formula is used and coming out be 63

---

63 is right ans

---

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

---

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.

Answer 1

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.

Answer 2

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 .