Are keys in B-tree nodes duplicated when the node is split?

Question

When a node in a B-tree is split, are keys from the original node duplicated in the new nodes? What's the purpose of doing this? Isn't this inefficient?

Answer 1

No. It's all done with pointers. Half of the pointers are moved to the new node.

Of course, there's no such thing as 'a B-tree'. There are a myriad of different implementations. I could imagine one in which the keys are actually stored in the nodes, such as a tree where the keys are ints. But they still wouldn't be 'duplicated', just the data copied.

If your beef is the storage left behind in the node that gets split, well, that's another optimization choice whether to free and reallocate smaller or not. Probably not, since more insertions could arrive that go into that node's 1/2 of the key space.

Answer 2

I think that you mean a B+ tree.

In a B+ tree that I wrote, I did duplicate the key values in the parent node during a split. key[pos] in the parent was set to the left node's lowest value and pointed to the left node. The right node's lowest value became key[pos+1] in the parent.