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 values of all keys in the subtree rooted at a child c_i are between the key values k_{i-1} and k_i that surround the pointer to c_i. Which of the following is TRUE about a B+ tree? A. What is the total number of key values in the internal nodes of a B+ tree with f leaves, if f >= 2? B. What is the maximum number of internal nodes in a B+ tree of order 4 with 32 leaves? C. What is the minimum number of leaves in a B+ tree of order d with height h(h >= 1)?

GATE 1997 · Databases · B Tree · medium

Answer: A: Total internal key values = f - 1 (one less than the number of leaves). B: Maximum number of internal nodes in a B+ tree of order 4 with 32 leaves = 10 (using minimum fanout of 5). C: Minimum number of leaves in a B+ tree of order d with height h = 2*(d+1)^(h-2) for h >= 2.

1. Part A: Total internal key values for f leaves: In a B+ tree, each internal key acts as a separator between two subtrees. With f leaves, there are f-1 separators in total across all internal nodes. This is analogous to a binary search tree where n-1 internal comparisons separate n items. Each key in an internal node corresponds to one 'split' between adjacent leaf ranges. Total internal keys = f - 1.
2. Part B: Maximum internal nodes for order 4, 32 leaves: Order 4 means each internal node has between 5 and 9 children (4 to 8 keys). To maximize internal nodes, use minimum fanout (5 children per node). Level above leaves: ceil(32/5) = 7 nodes. Level above that: ceil(7/5) = 2 nodes. Level above that: ceil(2/5) = 1 node (root). Total internal nodes = 7 + 2 + 1 = 10. But with maximum fanout 9: level above 32 leaves with fanout 9 = ceil(32/9) = 4 nodes. Then ceil(4/9) = 1 (root). Total = 4 + 1 = 5. The question asks for maximum, which uses minimum fanout: total = 7 + 2 + 1 = 10. However, if the question uses order 4 meaning 4 to 8 keys (5 to 9 children), then minimum fanout = 5: 32/5 = 7 nodes, 7/5 = 2 nodes, 2/5 = 1 node. Max internal nodes = 7 + 2 + 1 = 10. Actually with exactly 32 leaves and min fanout 5: first level above leaves has at least ceil(32/9)=4 and at most ceil(32/5)=7. For max internal nodes use min fanout: 7 + 2 + 1 = 10.
3. Part C: Minimum leaves for B+ tree of height h: Minimum leaves occur with the sparsest tree. Root has 1 key (2 children). Each non-root internal node has d keys (d+1 children, the minimum). At height h, there are h-1 levels of internal nodes above the leaves. Min leaves = 2 * (d+1)^(h-2) when height is measured from root to leaf (root=1, leaf=h). Actually: with root having 2 children and each subsequent internal node having d+1 children, at height h the minimum number of leaves = 2 * (d+1)^(h-2).