Why we are not saving the parent pointer in "B+ Tree" for easy upward traversal in tree?

Question

Will it affect much if I add a pointer to the parent Node to get simplicity during splitting and insertion process?

General Node would then look something like this :

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

What are the challenges I might get in real life database system since right now.

I am only implementing it as a hobby project.

I might be asking a dumb question I know but during implementation, I didn't find any! That's why I was wondering what could be the things I was missing? @MohamadShahrestani — Nitesh Kumar Tiwari, Sep 07 '19 at 05:57

score 2 · Accepted Answer · answered Sep 07 '19 at 15:15

There are two reasons I can think of:

The algorithm for deleting a value from a B+tree may result in an internal block A that has too few child blocks. If neither the block at the left or right of A can pass an entry to A in order to resolve this violation, then block A needs to merge into a sibling block B. This means that all the child blocks of block A need to have their parent pointer updated to block B. This is additional work that increases (a lot) the number of blocks that need an update in a delete-operation.
It represents extra space that is really not needed for performing the standard B+Tree operations. When searching a value via a B+Tree you can easily keep track of the path to that leaf level and use it for backtracking upwards in the tree.

This nails it. It is up to you whether the benefits of parent pointers justify it for your use case vs these (modest) disadvantages. — WestCoastProjects, Sep 07 '19 at 17:04

Why we are not saving the parent pointer in "B+ Tree" for easy upward traversal in tree?

1 Answers1