Basic Introduction to B-trees

Properties

1. They can hold up to 3 values in a node!
2. They always have one more children than values in a node.
3. Leftmost children is smaller than the lowest in a node, the second leftmost is bigger than the smallest but smaller than the second smallest in the parent node, and etc.

Pre-emptive splitting

• Pre-emptive splitting guarantees that there is always space in the parent to recieve a node from a full child.
• While traversing down a B-tree (during insertion), if a node is full, we want to split it so that we won't have to do it after splitting a possible full child node.
• If a root node is being split, then the middle child will become the new root node and the height increases by 1 (only time height increases!).

Other information:

1. If you are trying to insert into a node that is full, push the middle child into the parent. The least of the full node will be the left child of the middle node of the parent and vice versa for the biggest (goes to right child).
2. Insert only into leaf nodes!!! It works likes BST insertion, except you got the splitting going on.

See the link below for more information on this topic!