The two smallest B-trees you can build
A 2-3 tree is a B-tree of order 3. A 2-3-4 tree is a B-tree of order 4. Naming them separately is a teaching convenience — they follow exactly the rules from Lesson 2, just at the smallest useful sizes.
After this lesson
You should be able to
- Describe the two node shapes a 2-3 tree allows.
- Describe the three node shapes a 2-3-4 tree allows.
- Explain why these are named cases of the general B-tree from Lesson 2.
2-3 trees: two keys, three children, or one key, two
A 2-3 tree is named after its two allowed internal node shapes: a 2-node holds one key and two children, and a 3-node holds two keys and three children. That is simply order 3 from Lesson 2's B-tree definition — at most m - 1 = 2 keys, at most m = 3 children — given its own name because it is small enough to reason about by hand and is commonly taught before the general case.
Every rule from Lesson 2 applies unchanged: every leaf at the same depth, an overflowing node splits and pushes its middle key up. A 2-3 tree is not a different algorithm — it is the same algorithm at the smallest order where splitting is even possible.
2-node: 3-node:
[k] [k1 | k2]
/ \ / | \
<k >k <k1 k1-k2 >k22-3-4 trees: one order bigger
A 2-3-4 tree adds a third allowed shape: a 4-node, holding three keys and four children — exactly order 4 from Lesson 2, at most 3 keys and 4 children per node. It permits a node to grow one step bigger before it must split, which means slightly fewer splits during insertion in exchange for slightly more keys to scan within each node.
This is the same trade-off Lesson 1 introduced in the abstract, now visible at the smallest scale where you can trace it by hand: a bigger order means fewer, fatter nodes.
Why bother with two names for one idea
2-3 and 2-3-4 trees exist as teaching tools and as the conceptual ancestor of red-black trees from Unit II — a red-black tree's rules are, in fact, exactly a 2-3-4 tree in disguise, with a 3-node or 4-node's extra keys represented as red children hanging off a black one. Recognizing that connection is worth more than memorizing either structure separately.
Try it yourself
Insert 10, 20, 30 one at a time into an empty 2-3 tree, describing the split (if any) after each insertion.
Need a hint?
A 2-node can absorb one more key and become a 3-node without splitting. Only a 3-node overflows.
Check the worked solution
Inserting 10 gives a single 2-node [10]. Inserting 20 fills it to a 3-node [10, 20] — no split needed, since a 3-node is still legal. Inserting 30 would make it [10, 20, 30], four keys' worth of room in a node that only holds two — it splits at the middle key, 20, producing root [20] with children [10] and [30]. The tree grew from one level to two, uniformly, exactly as Lesson 2 described.
Quick check
A 2-3-4 tree is best understood as what?
Why this lesson exists
Syllabus mapping
2-3 Trees · 2-3- Tree
Maps to course outcomes CO1, CO4.