M-way Search Trees

A binary search tree lets each node hold one key and point to two children. An m-way search tree (also called a multiway search tree) simply raises those numbers: each node may hold many keys and point to many children.

Definition. An m-way search tree of order m is a tree in which every node has at most m children and at most m − 1 keys. The keys inside a node are kept in sorted order, and they partition the key space so that every child subtree falls into a specific range.

The number m is called the order (or degree) of the tree. A binary search tree is just an m-way search tree with m = 2.

Why bother? A taller-but-thinner binary tree needs many comparisons to reach a leaf. A shorter, bushier m-way tree reaches the same data in far fewer steps — which matters enormously when each "step" is a slow disk read (the motivation behind B-trees, covered in the next topics).

A node in an m-way search tree with k keys stores them interleaved with k + 1 child pointers:

The pointers sit between and around the keys, and each one guards a range:

• P0 → subtree with all keys < K1
• P1 → subtree with all keys between K1 and K2
• P_i → subtree with all keys between K_i and K_{i+1}
• P_k → subtree with all keys > K_k

This is the search invariant: reading the keys of any node left to right, and reading the subtrees between them, always produces sorted order. Searching works exactly like a BST — at each node you find the gap your target falls into and follow that one pointer down.

Consider a node in an m-way search tree of order 5. The maximum it can hold is m − 1 = 4 keys and m = 5 child pointers.

Say the four keys are 20, 40, 60, 80. Placed in sorted order, they carve the number line into five open regions — and each region needs its own subtree to hold values that land there:

Count the gaps: before 20, between 20 and 40, between 40 and 60, between 60 and 80, and after 80. Four keys create exactly five intervals, so the node needs five child pointers — one per interval.

The rule is general: k keys always split the key space into k + 1 ranges, so a node with k keys must have k + 1 child pointers. That is why "number of children = number of keys + 1" is the defining relationship of every multiway search node.

For a tree of order m:

Crucially, an ordinary m-way search tree has no balance rule. It only constrains the maximum size of a node — nothing forces nodes to be full or forces leaves to sit at the same depth. Insertions can produce a lopsided, tall tree, exactly like a naive BST built from sorted input. The next topic (B-trees) adds the missing balance invariants.

Let's construct an m-way search tree of order 4 (so at most 3 keys and 4 children per node) by inserting:

50, 20, 70, 10, 30, 60, 80, 25, 35, 65, 90

Insertion rule (plain m-way, no splitting): search for the key; if the leaf node it lands in still has room (< 3 keys), drop it in sorted position; otherwise create a new child in the correct range.

Is the final tree necessarily balanced? No. The shape depends entirely on insertion order. Here it happened to stay short, but feeding the keys in sorted order (10, 20, 25, 30, …) would have produced a long right-leaning chain of nodes — a plain m-way search tree has no mechanism to rebalance. Guaranteeing balance is precisely what B-trees add, using node splitting so that all leaves always end at the same depth regardless of insertion order.

Searching visits one node per level and does up to m − 1 key comparisons inside each node.

• Balanced m-way tree of n keys: height ≈ log_m(n), so search is O(log_m n · m) = O(m · log_m n).
• Degenerate (unbalanced) m-way tree: height can reach O(n) — the worst case a plain m-way tree does not prevent.

The takeaway: raising the order m flattens a balanced tree, but only an added balance invariant makes that flatness a guarantee.