用c++实现B树的插入

B树的插入操作相对比较复杂，需要考虑节点分裂、父节点的更新等情况。下面是一个简单的C++代码实现：

#include <iostream>
#include <vector>

using namespace std;

const int MAX_KEY_NUM = 3; // B树的阶数
const int MIN_KEY_NUM = MAX_KEY_NUM / 2;

// B树节点的结构体
struct BTreeNode {
    bool is_leaf; // 是否是叶子节点
    vector<int> keys; // 存储节点的所有关键字
    vector<BTreeNode*> children; // 存储子节点的指针
    BTreeNode(bool is_leaf=false) : is_leaf(is_leaf) {}
};

// 在B树的节点中查找关键字
int search_key(const vector<int>& keys, int key) {
    int left = 0, right = keys.size() - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (keys[mid] == key)
            return mid;
        else if (keys[mid] < key)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return left;
}

// 在B树中查找关键字
BTreeNode* search_node(BTreeNode* root, int key) {
    if (root == nullptr)
        return nullptr;
    int i = search_key(root->keys, key);
    if (i < root->keys.size() && root->keys[i] == key)
        return root;
    else if (root->is_leaf)
        return nullptr;
    else
        return search_node(root->children[i], key);
}

// B树节点的分裂操作
void split(BTreeNode* node, int i) {
    BTreeNode* right = new BTreeNode(node->is_leaf);
    right->keys.assign(node->keys.begin() + MIN_KEY_NUM + 1, node->keys.end());
    node->keys.resize(MIN_KEY_NUM);
    if (!node->is_leaf) {
        right->children.assign(node->children.begin() + MIN_KEY_NUM + 1, node->children.end());
        node->children.resize(MIN_KEY_NUM + 1);
    }
    node->children.insert(node->children.begin() + i + 1, right);
    node->keys.insert(node->keys.begin() + i, right->keys[0]);
}

// B树的插入操作
void insert(BTreeNode*& root, int key) {
    if (root == nullptr) {
        root = new BTreeNode(true);
        root->keys.push_back(key);
    } else {
        BTreeNode* node = root;
        BTreeNode* parent = nullptr;
        int i;
        while (node != nullptr) {
            i = search_key(node->keys, key);
            if (i < node->keys.size() && node->keys[i] == key)
                return;
            parent = node;
            node = node->children.empty() ? nullptr : node->children[i];
        }
        parent->keys.insert(parent->keys.begin() + i, key);
        if (parent->keys.size() > MAX_KEY_NUM) {
            int mid = MAX_KEY_NUM / 2;
            split(parent, mid);
            if (parent == root) {
                root = new BTreeNode(false);
                root->children.push_back(parent);
            }
            parent = parent->keys[mid];
        }
    }
}

这段代码实现了B树的插入操作，其中 `MAX_KEY_NUM` 表示B树的阶数， `MIN_KEY_NUM` 表示每个节点的最小关键字数。在插入操作时，需要考虑节点分裂的情况。