GATE CSE 1997 | Question: 19

Question

A $B^+$ - tree of order $d$ is a tree in which each internal node has between $d$ and $2 d$ key values. An internal node with $M$ key values has $M + 1$ children. The root (if it is an internal node) has between $1$ and $2d$ key values. The distance of a node from the root is the length of the path from the root to the node. All leaves are at the same distance from the root. The height of the tree is the distance of a leaf from the root.

• A. What is the total number of key values in the internal nodes of a $B^+$-tree with $l$ leaves ($l\geq 2$)?

• B. What is the maximum number of internal nodes in a $B^+$ - tree of order $4$ with $52$ leaves?

• C. What is the minimum number of leaves in a $B^+$-tree of order $d$ and height $h(h\geq 1)$?

Comments

If the order of a B+-Tree is 'd' then minimum and maximum number of keys it can have are ceil(d/2) - 1 and d - 1, respectively. How can they say that its between d and 2d? Can someone please explain it to me?

---

Plz see the definition of order that is mentioned in the question.So we should adhere and not confuse with the normal definition of order.Ya it is true that order is the number of child pointers by default but in this particular question, it is given to be the number of keys per node instead of no. of child pointers.Many have misunderstood this question on this very aspect.In such question,if definition of order is given , then use it else we use the default definition of order which is no. of child pointers per node.

~ by Habib Mohammad Khan (https://www.techtud.com/doubt/b-tree scroll down to see his comment in techtud.) 

---

For B part, i solved it in the following way.

$d=4$, $l=52$

We know that in B/B+ Tree # Leaf Nodes = # internal keys + 1

# internal keys = 51, from these give 1 key to root node.

We want maximum number of internal nodes so we distribute the remaining $50$ internal keys such that each node gets minimum number of keys.

Minimum number of keys a node can have  = $4$

and maximum number of keys a node can have  = $8$

$\lfloor \frac{50}{4} \rfloor=12$, why we took floor? coz the remainder $2$ keys couldn’t be in a node coz we need minimum $4$ keys in a valid node.

Total Internal Nodes = $12+1=13$

Answer 1

part(B)

Here order d=4 so the minimum number of keys per  node=4 as per question.Now applying the result from part a i.e total number of keys in internal nodes is l-1 if the number of leaves is l.

Here total number of keys in the internal nodes=52-1=51

Now maximum number of internal nodes possible will be ceil(51/4)=13