如何用C++递归模板定义层级异构的类B+树结构

需求概述 #

需要实现一种类B+树结构，核心特性：

• 各层级节点存储不同类型的数据（用于缓存场景）
• 每个层级的子节点最大数量各不相同
• 树结构在编译期通过模板静态配置，运行时无需修改

调整为合法C++语法后的期望实例化形式：

Tree<StructLeaf, NodeConfig<8, Struct1>, NodeConfig<16, Struct2>, NodeConfig<32, Struct3>> my_tree;

对应层级规则：

• 根节点：最多8个一级子节点，存储Struct1
• 一级节点：最多16个二级子节点，存储Struct2
• 二级节点：最多32个叶子节点，存储Struct3
• 叶子节点：存储StructLeaf

解决方案实现 #

1. 封装节点配置参数对 #

C++不支持直接传递“整型+类型”的参数对，因此先定义一个模板结构体，将每个非叶子节点的两个参数（子节点数、存储数据类型）打包成一个类型：

template<int ChildCount, typename NodeData>
struct NodeConfig {
    static constexpr int child_count = ChildCount; // 子节点最大数量
    using data_type = NodeData;                    // 当前节点存储的数据类型
};

2. 实现递归的Node类 #

通过模板递归生成不同层级的节点：

递归终止：叶子节点

当模板参数中没有剩余的NodeConfig时，即为叶子节点，直接存储叶子数据：

template<typename TLeafData>
class Node {
public:
    TLeafData data;
};

递归体：非叶子节点

处理带有至少一个NodeConfig的情况，提取当前节点的配置，并递归生成子节点类型：

template<typename TLeafData, typename CurrentConfig, typename... RemainingConfigs>
class Node<TLeafData, CurrentConfig, RemainingConfigs...> {
public:
    using Data = typename CurrentConfig::data_type;
    static constexpr int ChildCount = CurrentConfig::child_count;

    Data data;
    // 子节点数组：每个子节点是剩余配置递归生成的Node类型
    std::array<Node<TLeafData, RemainingConfigs...>, ChildCount> children;
};

3. 封装Tree类（可选） #

为了贴合用户期望的实例化语法，封装顶层的Tree类，本质是对顶层Node的包装：

template<typename TLeafData, typename... NodeConfigs>
class Tree : public Node<TLeafData, NodeConfigs...> {};

4. 完整实例化示例 #

// 定义示例数据结构体
struct StructLeaf {};
struct Struct1 {};
struct Struct2 {};
struct Struct3 {};

// 实例化符合需求的树
Tree<StructLeaf, NodeConfig<8, Struct1>, NodeConfig<16, Struct2>, NodeConfig<32, Struct3>> my_tree;

核心逻辑说明 #

• 参数传递：通过NodeConfig将“子节点数+数据类型”打包为单个类型参数，解决C++模板无法直接传递参数对的问题
• 递归展开：每次递归处理第一个NodeConfig，剩余参数传递给子节点模板，直到参数为空触发叶子节点特化
• 参数访问：通过CurrentConfig::data_type和CurrentConfig::child_count直接获取封装的类型和常量，避免模板模板参数无法内部访问的问题

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