面试题：C++ 中 B+ 树节点的基本结构如何设计

Question

在 C++ 中，为实现 B+ 树，请设计 B+ 树节点的基本结构，包括数据存储部分、指针部分等，需考虑到 B+ 树的特性，例如所有数据都存储在叶子节点等。给出相应的 C++ 代码实现。

Answer 1

#include <iostream>
#include <vector>
#include <memory>

// 定义B+树节点的最大关键字数
const int MAX_KEYS = 4;

// 定义B+树节点的最小关键字数
const int MIN_KEYS = (MAX_KEYS + 1) / 2 - 1;

// 数据类型
using KeyType = int;

// 前向声明
template <typename Key>
class BPlusTreeNode;

// B+树叶子节点类
template <typename Key>
class BPlusTreeLeafNode : public BPlusTreeNode<Key> {
public:
    std::vector<Key> keys;
    std::unique_ptr<BPlusTreeLeafNode<Key>> next;

    BPlusTreeLeafNode() : next(nullptr) {}

    // 判断叶子节点是否已满
    bool isFull() const {
        return keys.size() == MAX_KEYS;
    }

    // 获取叶子节点中的关键字数量
    size_t getKeyCount() const {
        return keys.size();
    }
};

// B+树内部节点类
template <typename Key>
class BPlusTreeInternalNode : public BPlusTreeNode<Key> {
public:
    std::vector<Key> keys;
    std::vector<std::unique_ptr<BPlusTreeNode<Key>>> children;

    BPlusTreeInternalNode() {}

    // 判断内部节点是否已满
    bool isFull() const {
        return keys.size() == MAX_KEYS;
    }

    // 获取内部节点中的关键字数量
    size_t getKeyCount() const {
        return keys.size();
    }
};

// B+树节点基类
template <typename Key>
class BPlusTreeNode {
public:
    virtual ~BPlusTreeNode() = default;
    virtual bool isLeaf() const = 0;
    virtual bool isFull() const = 0;
    virtual size_t getKeyCount() const = 0;
};