The function FindKey is to check if a given key is in a B+ Tree with its root pointed by root.
FindKey
key
root
Return true if key is in the tree, or false if not. The B+ tree structure is defined as following:
true
false
static int order = DEFAULT_ORDER; typedef struct BpTreeNode BpTreeNode; struct BpTreeNode { BpTreeNode** childrens; /* Pointers to childrens. This field is not used by leaf nodes. */ ElementType* keys; BpTreeNode* parent; bool isLeaf; /* 1 if this node is a leaf, or 0 if not */ int numKeys; /* This field is used to keep track of the number of valid keys. In an internal node, the number of valid pointers is always numKeys + 1. */ }; bool FindKey(BpTreeNode * const root, ElementType key){ if (root == NULL) { return false; } int i = 0; BpTreeNode * node = root; while (8 分) { i = 0; while (i < node->numKeys) { if (8 分) i++; else break; } node = node->childrens[i]; } for(i = 0; i < node->numKeys; i++){ if(node->keys[i] == key) return true; } return false; }