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

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?