Below is a partially implemented C code for searching within a $\mathrm{B}+$ tree in a database. The function search_bplus_tree() is responsible for finding a key within the tree.
Some parts of the code are missing. Your task is to choose the correct option to fill in the blanks.
Note that when the search key is equal to the key at index i in the current node, the search continues by following the right child pointer, which is children [ $i+1$ ]. This ensures that the search navigates into the correct subtree, as the actual data is stored in the leaf nodes.
typedef struct BPlusTreeNode {
int keys[order];
struct BPlusTreeNode* children[order + 1];
int is_leaf;
int num_keys;
} BPlusTreeNode;
int search_bplus_tree(BPlusTreeNode* root, int key) {
BPlusTreeNode* current_node = root;
while (!current_node->is_leaf) {
int i = 0;
// Traverse the node's keys to find the correct child node
while (_________1_________ && _________2_________) {
i++;
}
// Move to the appropriate child node
__-_-_-__3__-_-_-__-_;
}
// Perform search on the leaf node to find the key
for (int i = 0; i < current_node->num_keys; i++) {
if (current_node->keys[i] == key) {
return 1; // Key found
}
}
return 0; // Key not found
}
What condition should be the corner condition to break out of the loop? [2 marks]
- $\mathrm{i}<$ order
- $\mathrm{i}$ $<=$ order
- $\mathrm{i}$ $<$ current_node → num_keys $-1$
- $\mathrm{i}$ $<=$ current_node → num_keys $-1$
