B+ Tree data structure for keys

In a B+ Tree, I think there can be a maximum of M (the order of the B+Tree) - 1 keys for any given node.

Now when you want to insert a key with say value 7 into this tree with a order of 4:

10, 12  

Then it would become this:

7, 10, 12  

If the structure of a node is as such:

struct Node {      int keys[MAX_SIZE];      ...  };  

Then that would mean you have to shift at most MAX_SIZE elements to the right if you were to insert at the beginning of the node. This is not the most ideal. I was wondering if there was a better where to store keys. If you stored each key as a linked list, that would provide better insertion but it would cost a lot more space.

What is the best way to store keys? In my scenario this B+Tree will be used purely in memory.

https://stackoverflow.com/questions/67237034/b-tree-data-structure-for-keys April 24, 2021 at 05:27AM