A B+ tree of order d is a tree in which each internal node has between d and…
1997
A B+ tree of order d is a tree in which each internal node has between d and 2d 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 ≥ 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 ≥ 1)?
- A.
(a) l + 1 (b) 8 (c) 2(d + 1)^(h − 1)
- B.
(a) l − 1 (b) 13 (c) 2(d + 1)^(h − 1)
- C.
(a) l − 1 (b) 17 (c) 2(d − 1)^(h − 1)
- D.
(a) l − 1 (b) 9 (c) 2(d − 1)^(h + 1)
Attempted by 7 students.
Show answer & explanation
Correct answer: B
For part (a), let the internal nodes be I₁, I₂, ..., Iₘ, and suppose node Iⱼ has kⱼ key values. Then Iⱼ has kⱼ + 1 children. The total number of child pointers from internal nodes is therefore Σ(kⱼ + 1). These child pointers point to every non-root node: all l leaves plus the remaining m − 1 internal nodes.
So, Σ(kⱼ + 1) = l + (m − 1). Hence, Σkⱼ + m = l + m − 1, which gives Σkⱼ = l − 1. Thus the total number of key values in all internal nodes is l − 1.
For part (b), d = 4, so a non-root internal node has 4 to 8 keys and therefore 5 to 9 children. To maximize the number of internal nodes for 52 leaves, use the minimum possible fan-out. At the level just above the leaves, the maximum number of parent nodes is floor(52 / 5) = 10, and 52 leaves can be distributed among these 10 nodes within the allowed range. These 10 internal nodes cannot all be children of the root because the root can have at most 9 children. Therefore we need one more internal level: the root has 2 children, and those 2 internal nodes can have 5 children each. Total internal nodes = 1 + 2 + 10 = 13.
For part (c), the root has the minimum possible 2 children. Every non-root internal node has the minimum possible d + 1 children. For height h, this gives 2(d + 1)^(h − 1) leaves.
Therefore, the correct combination is (a) l − 1, (b) 13, (c) 2(d + 1)^(h − 1).