2-3-4 Trees: A Type of B Tree

Why B Trees?

Referencing a tree node requires a memory access, and memory access operations can be slow. The goal is to keep the number of memory accesses as low as possible. The solution is to increase the number of values stored in each node and increase the number of children at each node.

Definition

B Trees are self balancing trees where each node may have multiple children and multiple values. B Trees are not binary search trees, but they do follow an order property. 2-3-4 Trees are a kind of B tree where nodes can be 2 nodes, 3 nodes, or 4 nodes. Insertion in a B tree is always done in a leaf node. When a new level is needed, the tree grows at the root level.

Properties

Rules Every 2-3-4 Tree Follows

Leaf Depth All leaf nodes must be at the same depth level.
Children Count An internal node with n values has exactly n + 1 children.
Sorted Values The values inside each node must be sorted. For a node with values v1, v2, v3 we have v1 < v2 < v3.
Order Property All values in the subtree to the left of a value must be smaller than it, and all values in the subtree to the right must be larger than it.

Internal Node Types

2-Nodes, 3-Nodes, and 4-Nodes

2-Node 1 value, 2 children. Values less than v go left; values greater than v go right.
3-Node 2 values (v1, v2), 3 children. Values less than v1 go left; values between v1 and v2 go middle; values greater than v2 go right.
4-Node 3 values (v1, v2, v3), 4 children. Each subtree holds values in the range between its two surrounding keys.

Tree Diagram

A Sample 2-3-4 Tree

Diagram of a 2-3-4 tree showing a 4-node root with keys 10, 20, 30 and children that are 2-nodes and 3-nodes, with all leaves at the same depth. — All leaf nodes sit at the same depth. Internal nodes hold multiple values and have one more child than they have values.

Search Operation

How to Find a Value

Start at the first value in the root node and follow these steps at each value:

Compare the target value to the current node value.
If they are the same, the search is over and a match is found.
If the target is smaller, search the left subtree of the current value.
If the target is larger and there is another value to the right, compare with that value next.
If the target is larger and there is no value to the right, search the right subtree.
If there are no children, the search is over and no match was found.

Insert Operation

Pre-emptive Splitting

Pre emptive splitting is when we split full nodes along the search path during insertion. This keeps the tree balanced without needing to walk back up.

Search for where the new value should go.
For every node along the search path, check if the node is full (a 4 node). If it is, split it pre emptively before continuing.
Once we reach a leaf node it will always have an open spot because we split any full nodes on the way down. Add the new value there.