面试题：C++ 实现 B+ 树的插入操作

设计思路

节点结构设计：
- 内部节点：包含若干键值和指向子节点的指针。键值数量小于等于 m - 1（m 为节点的最大度数），子节点指针数量为键值数量加 1。
- 叶子节点：包含若干键值和指向记录的指针（这里简化为直接存储键值），以及一个指向下一个叶子节点的指针，用于顺序访问。键值数量小于等于 m - 1。
插入操作流程：
- 定位插入位置：从根节点开始，通过比较键值找到合适的叶子节点。
- 插入键值：在叶子节点插入键值，如果叶子节点未满（键值数量小于 m - 1），直接插入并保持节点有序。
- 节点分裂：如果叶子节点已满，将节点分裂为两个新的叶子节点。把中间键值提升到父节点，更新父节点的指针。如果父节点也满了，递归地分裂父节点，直到根节点。如果根节点分裂，创建一个新的根节点。

核心代码实现

#include <iostream>
#include <vector>

// 定义 B+ 树节点的最大度数
const int m = 3;

// 叶子节点结构体
struct LeafNode {
    std::vector<int> keys;
    LeafNode* next;
    LeafNode() : next(nullptr) {}
};

// 内部节点结构体
struct InternalNode {
    std::vector<int> keys;
    std::vector<InternalNode*> children;
    std::vector<LeafNode*> leafChildren;
    InternalNode() {}
};

// B+ 树类
class BPlusTree {
private:
    InternalNode* root;
    LeafNode* firstLeaf;

    // 叶子节点分裂
    void splitLeaf(LeafNode* leaf, int key) {
        LeafNode* newLeaf = new LeafNode();
        int mid = (m - 1) / 2;
        newLeaf->next = leaf->next;
        leaf->next = newLeaf;
        for (int i = mid; i < m - 1; ++i) {
            newLeaf->keys.push_back(leaf->keys[i]);
        }
        leaf->keys.resize(mid);
        if (key > newLeaf->keys[0]) {
            newLeaf->keys.insert(newLeaf->keys.begin(), key);
        } else {
            leaf->keys.push_back(key);
        }
    }

    // 内部节点分裂
    void splitInternal(InternalNode* internal, int key, LeafNode* leaf, int index) {
        InternalNode* newInternal = new InternalNode();
        int mid = m / 2;
        for (int i = mid; i < m; ++i) {
            newInternal->keys.push_back(internal->keys[i]);
            newInternal->children.push_back(internal->children[i]);
            if (i < m - 1) {
                newInternal->leafChildren.push_back(internal->leafChildren[i + 1]);
            }
        }
        internal->keys.resize(mid - 1);
        internal->children.resize(mid);
        internal->leafChildren.resize(mid);
        if (key > newInternal->keys[0]) {
            newInternal->keys.insert(newInternal->keys.begin(), key);
            newInternal->leafChildren.insert(newInternal->leafChildren.begin(), leaf);
            newInternal->children.insert(newInternal->children.begin(), internal->children.back());
        } else {
            internal->keys.push_back(key);
            internal->leafChildren.push_back(leaf);
            internal->children.push_back(newInternal->children[0]);
        }
    }

    // 向叶子节点插入键值
    void insertIntoLeaf(LeafNode* leaf, int key) {
        if (leaf->keys.size() < m - 1) {
            int i = leaf->keys.size() - 1;
            while (i >= 0 && key < leaf->keys[i]) {
                leaf->keys[i + 1] = leaf->keys[i];
                --i;
            }
            leaf->keys[i + 1] = key;
        } else {
            splitLeaf(leaf, key);
        }
    }

    // 向内部节点插入键值
    void insertIntoInternal(InternalNode* internal, int key, LeafNode* leaf) {
        if (internal->keys.size() < m - 1) {
            int i = internal->keys.size() - 1;
            while (i >= 0 && key < internal->keys[i]) {
                internal->keys[i + 1] = internal->keys[i];
                internal->children[i + 2] = internal->children[i + 1];
                internal->leafChildren[i + 1] = internal->leafChildren[i];
                --i;
            }
            internal->keys[i + 1] = key;
            internal->children[i + 2] = internal->children[i + 1];
            internal->leafChildren[i + 1] = leaf;
        } else {
            splitInternal(internal, key, leaf, 0);
        }
    }

    // 递归插入
    void insertRecursive(InternalNode* internal, int key) {
        if (internal->leafChildren.empty()) {
            int i = 0;
            while (i < internal->keys.size() && key > internal->keys[i]) {
                ++i;
            }
            insertRecursive(internal->children[i], key);
        } else {
            int i = 0;
            while (i < internal->keys.size() && key > internal->keys[i]) {
                ++i;
            }
            LeafNode* leaf = internal->leafChildren[i];
            insertIntoLeaf(leaf, key);
            if (leaf->keys.size() == m) {
                int mid = (m - 1) / 2;
                int newKey = leaf->keys[mid];
                LeafNode* newLeaf = new LeafNode();
                newLeaf->next = leaf->next;
                leaf->next = newLeaf;
                for (int j = mid + 1; j < m; ++j) {
                    newLeaf->keys.push_back(leaf->keys[j]);
                }
                leaf->keys.resize(mid);
                if (internal == root) {
                    InternalNode* newRoot = new InternalNode();
                    newRoot->keys.push_back(newKey);
                    newRoot->children.push_back(internal);
                    newRoot->children.push_back(new LeafNode());
                    newRoot->leafChildren.push_back(leaf);
                    newRoot->leafChildren.push_back(newLeaf);
                    root = newRoot;
                } else {
                    insertIntoInternal(internal, newKey, newLeaf);
                }
            }
        }
    }

public:
    BPlusTree() : root(nullptr), firstLeaf(nullptr) {}

    // 插入接口
    void insert(int key) {
        if (root == nullptr) {
            LeafNode* newLeaf = new LeafNode();
            newLeaf->keys.push_back(key);
            firstLeaf = newLeaf;
            root = new InternalNode();
            root->leafChildren.push_back(newLeaf);
        } else {
            insertRecursive(root, key);
        }
    }
};

星途面试题库

面试题：C++ 实现 B+ 树的插入操作

知识考点

面试题答案

设计思路

核心代码实现