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

Comments

It should be 63.

p(9+7) + 6 <= 1024

P = 63.

---

Thanks. I also got 63 but the answer given was 64 with the explanation as (p-1)(9+7) + 6 <= 1024 and so i just wanted to clarify.

---

Haha! Many times they mixed up B and B+ tree concepts for these crucial answers ! and unnecessarily it confuses us! :(

---

@Ashwin Kulkarni : you are taking $P$ pointers to data records and $1$ more for next block but that constitutes to $P+1$ pointers which is contradicting the order of a block.
 

Source : Navathe : $6^{th}$ edition Page no 653

---

@saxena, I did the same way as diagram shows.

P <key,record> pairs and 1 block pointer for the next block.

And order of leaf will be number of <key,record> pairs in it!

---

Yup ! you are correct I erroneously counting the block pointer in order which is not the case. Thanks!

---

Block Size = 1024 bytes

Record pointer = 7 bytes

Block pointer = 6 bytes

Search keys = 9 bytes
Then,
= $(p-1) * (Record pointer + Key size) + Block Pointer \leq Block Size$

= (p-1) * (7+9) + 6 ≤ 1024

= (p-1) * (16) ≤ 1024 -6
=16p - 16 ≤ 1018

= 16p ≤ 1034

p ≤ 1034/16 = 64.625 = 64

So, the answer should be 64 right?How it is 63?

---

you are taking wrong formula.

For a B+ tree the order of a node is the maximum number of keys that it can contain.

for B+ tree

if p is the order then

in leaf node there are p <key,record pointer> and 1 block pointer.

(p)∗(Recordpointer+Keysize)+BlockPointerSize ≤ BlockSize

---

Okay. Thank you!

Answer 1

Comments

Can you please give general formula for both B-tree and B+tree and for leaf as well as non-leaf nodes?