(also called B-tree of order 4)

why?

a lot of the cost associated with a binary search tree comes from traversing the tree

2-3-4 trees try to fix this by storing more data items per node and allowing up to 4 children per node (has $\log_4(n)$ rather than $\log_2(n)$)

structure

a 2-3-4 tree has one of 3 types of nodes:

the items within each node are sorted

❗️it is impossible to have a 3-node with only 2 children and 2 items, or a 4-node with < 4 children but 3 items

rules