Question 16

The query asks for all records with key $7 \le k < 15$.

Step 1: Traverse the tree index to locate the lower bound key $7$.

• Fetch Node 1 (Root [9 | -]): Since $7 < 9$, follow the left child pointer.
• Fetch Node 2 (Internal node [5 | -]): Since $7 \ge 5$, follow the right child pointer.
• Fetch Node 3 (Leaf node [5 | 7]): Key $7$ is found in this leaf node.

Step 2: Traverse leaf sibling pointers to retrieve subsequent keys in the range $[7, 15)$:

• Follow the sibling pointer to Fetch Node 4 (Leaf node [9 | 11]): Both keys $9$ and $11$ satisfy $7 \le k < 15$.
• Follow the sibling pointer to Fetch Node 5 (Leaf node [13 | 15]): Key $13$ satisfies $7 \le k < 15$. Key $15$ violates $k < 15$, terminating the range scan.

Total nodes fetched = $1\text{ (root)} + 1\text{ (internal)} + 3\text{ (leaves)} = 5\text{ nodes}$.