C++实现B树时，节点是否应包含父节点指针？

节点分裂流程理解 #

1. 尝试将新值V插入叶子节点N
2. 若叶子节点无空间，创建新节点，选取N的中间值，将中间值右侧内容移至新节点，左侧内容保留并左移，将V插入拆分后的合适节点
3. 将中间值插入N的父节点，同时将新节点加入父节点的子节点列表（使二者成为兄弟节点）
4. 若N的父节点无空闲空间，执行相同拆分操作，同时拆分其子节点（此步骤仅适用于非叶子节点）
5. 持续将上一次拆分的中间值插入父节点，直至到达根节点，可能需拆分根节点创建新根

关于向上遍历的疑问 #

在实现过程中产生疑问：如何向上遍历？是否应当保留父节点指针？因为只有到达叶子节点插入时才能判断是否需要拆分，拆分后需回溯至父节点，若父节点也需拆分则需继续向上，否则每次都要重新遍历树寻找父节点。

节点类示例 #

template<typename KEY, typename VALUE, int DEGREE>
struct BNode
{
    KEY Keys[DEGREE];
    VALUE Values[DEGREE];

    BNode<KEY, VALUE, DEGREE>* Children[DEGREE + 1];
    BNode<KEY, VALUE, DEGREE>* Parent;

    bool IsLeaf;
};

另外，我考虑是否不应保留IsLeaf字段，而是通过检查是否存在子节点来节省空间。

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