It seems the non_leaf_split_right1 function has a bug.

[mohit84]

Let's suppose the non_leaf node has 3 entries 7, 17, 25, and max_order of the tree is 3. If suppose a non_leaf node has received a split node request from children for key 20.

Non_leaf_node : 7, 17, 25 split_key: 20 split_index = 2(3 + 1 ) / 2 split_key = 17 pivot = 0 node->children = 2 right->children = 2 right_node[0] = 20

Ideally right_node[1] key should be 25 but as per the condition memmove(&key(right)[pivot + 1], &key(node)[split], (right->children - 2) * sizeof(key_t)); no key will be copied to right[1] because the number of elements will be 0.

I think It should be right->children - 1. Please correct me if I am wrong.

static key_t non_leaf_split_right1(struct bplus_tree tree, struct bplus_node node, struct bplus_node right, struct bplus_node l_ch, struct bplus_node *r_ch, key_t key, int insert) { int i;

    /* split = [m/2] */
    int split = (_max_order + 1) / 2;

    /* split as right sibling */
    right_node_add(tree, node, right);

    /* split key is key[split - 1] */
    key_t split_key = key(node)[split - 1];

    /* calculate split nodes' children (sum as (order + 1))*/
    int pivot = 0;
    node->children = split;
    right->children = _max_order - split + 1;

    /* insert new key and sub-nodes */
    key(right)[0] = key;
    sub_node_update(tree, right, pivot, l_ch);
    sub_node_update(tree, right, pivot + 1, r_ch);

    /* sum = right->children = 2 + (right->children - 2) */
    /* replicate from key[split] to key[_max_order - 2] */
    memmove(&key(right)[pivot + 1], &key(node)[split], (right->children - 2) * sizeof(key_t));
    memmove(&sub(right)[pivot + 2], &sub(node)[split + 1], (right->children - 2) * sizeof(off_t));

}

[mohit84]

I am closing it because it is not an issue. It was my fault to missed one point in core, the internal node has 1 element less than the external nodes so it will work fine.