Which of the following data structure has the least height?

Concept. A B-tree of order m is a balanced multi-way search tree: every node stores at most m − 1 keys and has at most m children, and every internal node other than the root has at least ⌈m/2⌉ children. All leaves sit on the same level, so the height of such a tree is bounded by exactly two things — its order m and the number of keys n it has to store — and among the shapes a given m and n allow, the tightest packing is the shortest.

1. Level 0 holds 1 node, level 1 holds up to m nodes, and level 2 holds up to m2 nodes — each level multiplies the node count by at most m.

2. A tree of height h therefore holds at most 1 + m + m2 + … + mh nodes, which can index at most mh+1 − 1 keys.

3. Solving mh+1 − 1 ≥ n for h gives the shallowest legal shape, h ≥ ⌈logm(n + 1)⌉ − 1.

4. The sparsest legal shape gives the opposite bound: the root may keep just 2 children and every other internal node only ⌈m/2⌉, so h ≤ log⌈m/2⌉((n + 1)/2).

Application. Every choice here is a tree of the same family over the same set of keys, so the only variable is the order m. Both bounds move the same way as m grows: ⌈logm(n + 1)⌉ − 1 falls, and log⌈m/2⌉((n + 1)/2) never rises. Comparing the four structures at their tightest packing — the reading that a “least height” comparison assumes — a larger order can therefore never need more levels than a smaller one for the same keys.

Putting the four offered orders side by side for an illustrative load of n = 1,000,000 keys:

Cross-check. Check the extremes independently: with order 3 each level multiplies the node count by at most 3, so about log3(106) ≈ 12.6 levels of branching are needed to reach a million keys, while with order 6 each level multiplies by up to 6, so about log6(106) ≈ 7.7 levels are enough.

Three honest qualifications. First, the separation is not strict at every key count: for small key counts several orders share the same minimum height, and with 6 keys all four of them need height 1. Second, the worst-case bound uses the minimum branching ⌈m/2⌉, which equals 3 for both order 5 and order 6, so those two share the same upper bound. Third, because the exact shape depends on the insertion history, a sparsely filled high-order tree can be taller than a densely filled low-order one, which is why the comparison is made at equal packing. None of these lets a smaller order win: at equal packing a larger order never needs more levels than a smaller one.

Result. Of the four offered structures the one of order 6 has the largest branching factor, so at equal packing it never needs more levels than the rest, and for large key counts it needs strictly fewer — a million keys fit into 8 levels instead of the 13 that order 3 requires. The B-tree of order 6 therefore has the least height.