void splitChild(BTreeNode<T, M>* parent, int i) {
    BTreeNode<T, M>* fullChild = parent->children[i];
    BTreeNode<T, M>* newNode = new BTreeNode<T, M>(fullChild->isLeaf);
    newNode->n = (M - 1) / 2;

    // 拷贝后半部分关键字到新节点
    for (int j = 0; j < newNode->n; ++j)
        newNode->keys[j] = fullChild->keys[j + (M / 2)];

    if (!fullChild->isLeaf) {
        // 如果是非叶子，复制子节点指针
        for (int j = 0; j <= newNode->n; ++j)
            newNode->children[j] = fullChild->children[j + (M / 2)];
    }

    // 调整原节点数量
    fullChild->n = (M - 1) / 2;

    // 将新节点插入父节点
    for (int j = parent->n; j > i; --j)
        parent->children[j + 1] = parent->children[j];

    parent->children[i + 1] = newNode;

    for (int j = parent->n - 1; j >= i; --j)
        parent->keys[j + 1] = parent->keys[j];

    parent->keys[i] = fullChild->keys[(M / 2) - 1];
    parent->n++;
}

void insertNonFull(BTreeNode<T, M>* node, const T& key) {
    int i = node->n - 1;

    if (node->isLeaf) {
        // 找到插入位置并插入
        while (i >= 0 && node->keys[i] > key) {
            node->keys[i + 1] = node->keys[i];
            --i;
        }
        node->keys[i + 1] = key;
        node->n++;
    } else {
        // 找到对应的子节点
        while (i >= 0 && node->keys[i] > key)
            --i;
        ++i;

        // 若子节点满，则先分裂
        if (node->children[i]->n == M - 1) {
            splitChild(node, i);
            if (node->keys[i] < key)
                ++i;
        }
        insertNonFull(node->children[i], key);
    }
}

public: BTree() { root = new BTreeNode(true); }

void insert(const T& key) {
    BTreeNode<T, M>* r = root;

    // 根节点满时需分裂并创建新根
    if (r->n == M - 1) {
        BTreeNode<T, M>* s = new BTreeNode<T, M>(false);
        s->children[0] = r;
        root = s;
        splitChild(s, 0);
        insertNonFull(s, key);
    } else {
        insertNonFull(r, key);
    }
}</font>

查找功能实现

添加一个查找函数来验证插入是否正确。

    int i = 0;
    while (i < node->n && key > node->keys[i])
        ++i;

    if (i < node->n && key == node->keys[i])
        return true;

    if (node->isLeaf)
        return false;

    return search(key, node->children[i]);
}</font>