B Plus Tree Practice Questions

The $B^+$ tree has a maximum of 3 key values per node, meaning each node can hold up to $m-1=3$ keys, so the order $m$ is 4. This implies each node can have at most $m=4$ children.

1. Initial State: The root node contains keys {6, 12, 19}. The leaf node to the right of 19 contains {20, 21, 22}.
2. Insertion of 23: To insert 23, we navigate to the leaf node {20, 21, 22}.
3. Leaf Node Split: After inserting 23, this leaf node becomes {20, 21, 22, 23}. Since it exceeds the maximum of 3 keys, it splits. The middle key (21) is promoted to the parent, and two new leaf nodes are formed: {20} and {22, 23}.
4. Root Node Split: The promoted key (21) needs to be inserted into the root node {6, 12, 19}. After insertion, the root becomes {6, 12, 19, 21}. This also exceeds the maximum of 3 keys, so the root node splits. The middle key (19) is promoted to a new parent (the new root).
5. New Root and Increased Height: The new root node will contain {19}. The original root node splits into {6, 12} and {21}, becoming children of the new root. This process increases the height of the $B^+$ tree. Thus, at least one node splits (the leaf node and the original root), and the height of the tree increases.

[CORRECT_OPTION: B, D]

In a B+ tree, the requirement of at least half-full (50%) node occupancy applies to all nodes except the root node.
The root node of a B+ tree can have a minimum of two children (and thus one key) even if it means it is less than half-full. This relaxation is necessary to allow the tree to grow and shrink without strict minimum occupancy constraints at the very top.
All internal nodes (non-root, non-leaf) and leaf nodes must adhere to the 50% occupancy rule.
Therefore, the relaxation of the half-full requirement is specifically for the root node.

A B+ tree is defined as a balanced tree because the path length from the root to every leaf node is identical. This structural property ensures that all leaf nodes reside at the same depth or level. Consequently, the time taken to access any record is uniform and predictable, as it avoids the performance degradation that can occur in unbalanced trees where some branches are much longer than others.

To find all records with a search key $\ge 7$ and $< 15$, we must traverse the B+ tree.

1. Start at the root node (containing 9). Since 7 < 9, we traverse to the left child. (1st fetch)
2. The next node contains 5. Since 7 > 5, we traverse to the right child. (2nd fetch)
3. We reach the leaf node containing keys 5 and 7. (3rd fetch)
4. From this leaf, we scan sequentially using the sibling pointers. We fetch the next leaf node containing 9 and 11. (4th fetch)
5. We fetch the final required leaf node containing 13 and 15. (5th fetch)
   The search stops here. In total, 5 nodes are fetched.

To determine the minimum number of keys in a non-root node of a B+ tree, we first need to find the order of the tree.

1. The order of a B+ tree, let's call it p, is defined as the maximum number of children (or pointers to children) an internal node can have. The maximum number of keys in any node is p - 1.

2. We are given that the maximum number of keys is 5.
   So, p - 1 = 5, which means the order of the tree p = 6.

3. For a B+ tree of order p, any non-root node must be at least half-full. The rule for the minimum number of keys in a non-root internal node is ⌈p/2⌉ - 1.

4. Let's calculate this minimum:
   Minimum keys = ⌈6/2⌉ - 1
   Minimum keys = 3 - 1 = 2.

Note: For a non-root leaf node, the minimum number of keys is ⌊p/2⌋, which would be ⌊6/2⌋ = 3. The question asks for the minimum in any non-root node, so we take the smaller of the two minimums, which is 2.

The B+ tree has an internal node order of $m=3$ (max 2 keys, 3 pointers) and a leaf node order of $L=2$ (max 2 data items). We count leaf node splits.

1. Insert 10: Leaf node: $[10]$. (0 splits)
2. Insert 3: Leaf node: $[3, 10]$. (0 splits)
3. Insert 6: Leaf node $[3, 10]$ is full. Insert 6. It becomes $[3, 6, 10]$. This node splits.
   New leaf nodes: $[3, 6]$ and $[10]$. Key $6$ is promoted.
   Tree: Root: $[6]$ pointing to $[3, 6]$ and $[10]$. (1 split)
4. Insert 8: Search for 8, goes to leaf $[10]$. Insert 8. Leaf node: $[8, 10]$. (0 splits)
5. Insert 4: Search for 4, goes to leaf $[3, 6]$. Insert 4. It becomes $[3, 4, 6]$. This node splits.
   New leaf nodes: $[3, 4]$ and $[6]$. Key $4$ is promoted.
   The parent internal node $[6]$ now has keys $[4, 6]$ (max 2 keys). Its pointers are to $[3, 4]$, $[6]$, $[8, 10]$ (max 3 pointers).
   Current structure: Root $[4, 6]$ pointing to leaves $[3, 4]$, $[6]$, $[8, 10]$. (1 + 1 = 2 splits)
6. Insert 2: Search for 2, goes to leaf $[3, 4]$. Insert 2. It becomes $[2, 3, 4]$. This node splits.
   New leaf nodes: $[2, 3]$ and $[4]$. Key $3$ is promoted.
   The parent internal node $[4, 6]$ needs to incorporate $3$. Its keys would become $[3, 4, 6]$ (3 keys). This node is full, so it splits. Key $4$ is promoted to a new root.
   Tree: New Root: $[4]$. Left child (internal node): $[3]$ pointing to $[2, 3]$ and $[4]$. Right child (internal node): $[6]$ pointing to $[6]$ and $[8, 10]$. (2 + 1 = 3 splits)
7. Insert 1: Search for 1, goes to leaf $[2, 3]$. Insert 1. It becomes $[1, 2, 3]$. This node splits.
   New leaf nodes: $[1, 2]$ and $[3]$. Key $2$ is promoted.
   The parent internal node $[3]$ needs to incorporate $2$. Its keys become $[2, 3]$ (2 keys). This node is not full. Its pointers are to $[1, 2]$, $[3]$, $[4]$ (3 pointers).
   Current structure is valid. (3 + 1 = 4 splits)

The maximum number of times leaf nodes would get split up is $4$.

The final answer is $\boxed{C}$

Initially, the tree has leaf nodes $[K10, K20]$, $[K30]$, $[K40]$, and $[K50]$.

1. Inserting $K15$ causes leaf $[K10, K20]$ to become $[K10, K15, K20]$, which splits into $[K10]$ and $[K15, K20]$, promoting $K15$ to the parent.
2. Inserting $K25$ makes leaf $[K15, K20]$ become $[K15, K20, K25]$, which splits into $[K15]$ and $[K20, K25]$, promoting $K20$ to the parent.
3. This promotion forces the parent $[K15, K30]$ to split into $[K15]$ and $[K30]$, and $K20$ moves to the root, forming $[K20, K40]$.
4. Comparing the resulting tree against the provided set of nodes $\{[K30, K50], [K25, K30], [K20, K25], [K15, K20]\}$, only node $[K20, K25]$ remains.
   Thus, exactly $1$ node from the given set is present in the final tree.

The insertion of $K15$ into the leaf containing $\{K10, K20\}$ causes a split into $\{K10\}$ and $\{K15, K20\}$, promoting $K15$ to the parent. Subsequently, inserting $K25$ causes the parent $\{K15, K30\}$ to split, promoting $K20$ to the root, which becomes $\{K20, K40\}$. The deletion of $K50$ is handled within the leaf and parent nodes without causing underflow that cascades to the root; therefore, the tree height remains unchanged, making statement (i) true. Since the root node changes from $\{K40\}$ to $\{K20, K40\}$ during the insertions, statement (iii) is false. Thus, statements (i) and (ii) are true.

In a $B^+$ tree, all data records are stored exclusively in the leaf nodes, which are connected via a linked list. This structure enables efficient range queries because, after locating the starting key in $O(\log_b N)$ time-where $b$ is the branching factor and $N$ is the number of records-the system performs a linear scan across the leaves. Conversely, a standard B-tree stores keys and data in both internal and leaf nodes, requiring costly tree traversals for range retrieval. Option A is false as both structures optimize disk I/O, C is not a strict rule, and D is incorrect because tree height grows logarithmically with the number of records ($O(\log_b N)$). Thus, $B^+$ trees provide superior performance for range queries.