The Gatebook

Question

Here answer is 42 I think because we take floor of the value? Can some one confirm it??

Answer 1

In B+ tree the order of root and internal nodes and order of leaves is different.

If we take case of leaves

N * (key + block pointer) + 1 block pointer linking to next leaf $\leq$ Disk block size      (N = order of leaves)

N * (8+4) + 4 $\leq$ 512

12N $\leq$ 508

N = floor value (508/12)

N = 42

If we take case of root and internal nodes

N* size of block pointer + (N-1)* key $\leq$ Disk block size         (N = order)

4N + (N-1) 8 $\leq$ 512

N= floor value (520/12)

N=43

Comments

So here they asked for the tree so I have to calculate internal nodes order??

---

Maximum times they'll clearly mention it. If not then we should calculate internal node's or root node's order.

There is no problem with B tree, only problem with B+ tree because they differ in orders of leaves and non leaf nodes as above mentioned.

Answer 2

Key size = 8 byte

Disk block size = 512 byte

Block Pointer = 4 Byte

Internal node structure of B+ tree

P* size of block pointer + (P-1)[key] <= Disk block size         {P=order i.e #f block pointer}

4P + (P-1) [8] <= 512

P= Floor value (520/12)

P=43

Comments

@Akash Mittal The value should be floor. Because we are taking $\leq$ value

---

typo!