algorithm - 为什么我们不将父指针保存在“B+树”中以便在树中轻松向上遍历？

Question

如果我添加一个指向父节点的指针以在拆分和插入过程中变得简单，它会影响很大吗？

通用节点看起来像这样：

class BPTreeNode{
    bool leaf;
    BPTreeNode *next;
    BPTreeNode *parent; //add-on
    std::vector < int* >pointers;
    std::vector < int >keys;
};

从现在开始，我在现实生活中的数据库系统中可能会遇到哪些挑战。

我只是将它作为一个爱好项目来实施。

Answer 1

我能想到的原因有两个：

1. 从 B+树中删除值的算法可能会导致内部块 A 的子块太少。如果 A 左侧或右侧的块都不能向 A 传递条目以解决此违规问题，则块 A 需要合并到兄弟块 B 中。这意味着块 A 的所有子块都需要拥有自己的父指针更新到块 B。这是额外的工作，会增加（很多）需要在删除操作中更新的块的数量。

2. 它表示执行标准 B+Tree 操作实际上不需要的额外空间。通过 B+Tree 搜索值时，您可以轻松地跟踪到该叶级别的路径并将其用于在树中向上回溯。