Function tree_find_leaf

python/bplustree_c_src/tree_ops.c:11–40

Find leaf node that should contain the key */ Find leaf node that should contain the key */

/* Find leaf node that should contain the key */
/* Find leaf node that should contain the key */
BPlusNode* tree_find_leaf(BPlusTree *tree, PyObject *key) {
    BPlusNode *node = tree->root;
    
    while (node->type == NODE_BRANCH) {
        int pos = node_find_position(node, key);
        if (pos < 0) {
            return NULL;
        }
        /* bisect_right semantics: advance past equal keys */
        if (pos < node->num_keys) {
            PyObject *node_key = node_get_key(node, pos);
            int eq = fast_compare_eq(node_key, key);
            if (eq < 0) {
                return NULL;
            }
            if (eq) {
                pos++;
            }
        }
        /* Ensure pos is within valid child range */
        if (pos > node->num_keys) {
            return NULL;
        }
        {
            node = node_prefetch_child(node, pos);
        }
    }
    
    return node;
}

/* Recursive insert helper */
static int tree_insert_recursive(BPlusNode *node, PyObject *key, PyObject *value,