如何实现B树非抢占式分裂插入并避免根节点过早分裂？

问题根源 #

当前insertKey函数的逻辑错误：只要根节点的键数量达到KEYS_NUMBER就提前分裂根节点，无论插入操作是否需要修改根节点。在你的场景中，插入15仅需修改最右侧的叶子节点（该节点未满），完全不需要修改根节点，这种提前分裂属于不必要的操作。

核心优化思路 #

放弃根节点的提前分裂逻辑，改为延迟分裂：仅当节点插入键后超出容量（n = KEYS_NUMBER + 1）时，才触发分裂操作。这样只有当插入操作确实需要修改节点（包括根节点）且节点无法容纳新键时，才会进行分裂。

具体代码调整 #

1. 修改insertKey函数 #

移除根节点满即分裂的前置逻辑，改为直接插入，仅在根节点插入后溢出时处理分裂：

void insertKey(Node **tree, int key) {
    Node *r = *tree;
    // 直接插入，由insertNonFull处理节点满的情况
    insertNonFull(r, key);

    // 根节点插入后溢出，触发分裂
    if (r->n == KEYS_NUMBER + 1) {
        Node *s = createNode();
        *tree = s;
        s->leaf = false;
        s->n = 0;
        s->children[0] = r;
        splitChild(s, 0, r);
    }
}

2. 修改insertNonFull函数 #

调整逻辑，允许处理满节点：先完成插入操作，再检查子节点是否溢出并处理分裂：

void insertNonFull(Node *node, int key) {
    int i = node->n - 1;

    if (node->leaf) {
        // 叶子节点直接插入，即使满了也先容纳（后续由父节点处理分裂）
        while (i >= 0 && key < node->keys[i]) {
            node->keys[i + 1] = node->keys[i];
            i--;
        }
        node->keys[i + 1] = key;
        node->n = node->n + 1;
    } else {
        while (i >= 0 && key < node->keys[i]) {
            i--;
        }
        i++;
        // 递归插入子节点，不提前检查子节点是否满
        insertNonFull(node->children[i], key);

        // 子节点插入后溢出，触发分裂
        if (node->children[i]->n == KEYS_NUMBER + 1) {
            splitChild(node, i, node->children[i]);
        }
    }
}

3. 适配splitChild函数 #

修改分裂逻辑，处理插入后溢出的节点（n = KEYS_NUMBER + 1）：

void splitChild(Node *parent, int index, Node *child) {
    Node *newChild = createNode();
    newChild->leaf = child->leaf;
    newChild->n = MIN_KEYS;

    // 复制子节点的后MIN_KEYS个键到新节点
    for (int j = 0; j < MIN_KEYS; j++) {
        newChild->keys[j] = child->keys[j + MIN_KEYS + 1];
    }

    // 非叶子节点复制子指针
    if (!child->leaf) {
        for (int j = 0; j < MIN_KEYS + 1; j++) {
            newChild->children[j] = child->children[j + MIN_KEYS + 1];
        }
    }

    // 调整父节点的键和子节点数组
    child->n = MIN_KEYS;
    for (int j = parent->n; j > index; j--) {
        parent->keys[j] = parent->keys[j - 1];
        parent->children[j + 1] = parent->children[j];
    }
    parent->keys[index] = child->keys[MIN_KEYS];
    parent->children[index + 1] = newChild;
    parent->n = parent->n + 1;
}

效果验证 #

插入15时，最右侧叶子节点的键数量从2变为3（未超过KEYS_NUMBER=4），不会触发分裂；根节点始终未被修改，保持原结构，符合预期的结果：

[3, 6, 9, 12]
    [1, 2]
    [4, 5]
    [7, 8]
    [10, 11]
    [13, 14, 15]

内容的提问来源于stack exchange，提问作者Bole