algorithm - 为什么不把父指针保存在 "B+ Tree"，方便树向上遍历？

Question

如果在拆分和插入过程中添加指向父节点的指针以简化操作，是否会影响很大？

General Node 看起来像这样:

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

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

我只是将其作为业余爱好项目实现。

Answer 1

我能想到的原因有两个:

1. 从B+树中删除一个值的算法可能会导致内部 block A的子 block 太少。如果 A 左侧或右侧的 block 都不能将条目传递给 A 以解决此违规，则 block A 需要合并到同级 block B。这意味着 block A 的所有子 block 都需要拥有它们的父指针更新到 block B。这是额外的工作，会增加(大量)删除操作中需要更新的 block 的数量。

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