B-tree Insertion

Question

An order 3 B-tree is an index tree where every node other than root has at most 2 keys and at least one key. Starting with an empty tree if following keys are inserted into the tree 1,2,3,4,5,6,7,8,9,10. (not necessarily in the given order.) What would be the minimum number of node splits possible, if node splitting algorithm is used?

Answer 1

Insert in such a way that it will build as Full B- Tree since Order given 3 so we can insert at most 2 keys per node.

Full B- Tree contains root with 1 element, left subtree with 4 or 5 elements, right subtree with 4 or 5 elements.

For 10 nodes height is 3 so only 3 splits needed. 

NOTE: Always Select a middle element for new Insert.

Comments

I am getting 4 splits.

@papesh sir, please provide the exact sequence in which values should be inserted to get 3 splits.