splitting a B+ tree root -

when splitting root node of b+ tree know take n/2 +1 , make new root , split accordingly.

my question lies when n equal odd number. in case, n = 5.

so lets use simple example:

   10  20  30  40   /   |   |   |   \ 

where of children null. lets want add 50 this.

would like

       30       /  \ (10,20)   (40,50)  

or

           40           /  \  (10,20,30)  (50) 

or different?

if split node contains n keys - including incoming key caused split - (n - 1) / 2 keys go 1 new child, n - 1 - (n - 1) / 2 go other, , 1 key goes parent level (as separator key). key goes not same 1 caused split. if there separator go have new root , separator key single lone occupant (the minimum occupancy requirement not apply root nodes).

of course, formulae friendlier if @ rest remains after taking out new separator: r = n - 1 gives r / 2 1 side , r - r / 2 other.

in other words, under normal circumstances both 'halves' differ @ one, occur if total key count , hence leaves odd rest when separator key taken out. not matter whether key goes left or right.

however, not hammered in stone. there other valid redistribution strategies, notably knuth's b* 2 full nodes make 3 nodes 2/3rds full, , on. shows split/merge logic tied redistribution measures not change structure, i.e. donation , borrowing of keys between siblings.