2-3-4 B-Trees

2-3-4 Tree rules

• No node will exceed three contained elements
• Each internal node will have (numNodes) + 1 children
• All leaf nodes will be at the same height
• Each node will have its elements linearly ordered

2-3-4 Insertion algorithm

1. Start at root node
2. Perform a linear search to place to determine where in the current node the new value will fall
3. If current node was full before starting, split this node and retrace from root
4. If at an internal node, descend into appropriate subtree and repeat from step 2
5. If at a leaf node, perform a linear insertion

Click here for more information about B-Trees