为什么我们不将父指针保存在"B+ Tree"中以便于在树中向上遍历？

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+树操作实际上不需要的额外空间。通过 B+Tree 搜索值时，您可以轻松跟踪到该叶级别的路径，并使用它来在树中向上回溯。