A B-tree keeps every leaf at the same depth
A B-tree adds strict rules to the multi-way idea from Lesson 1 — a minimum fill per node and, crucially, every leaf sitting at exactly the same depth — so worst-case search never surprises you.
After this lesson
You should be able to
- State the structural rules that define a B-tree of a given order.
- Explain why every leaf sits at the same depth.
- Trace what happens to a node that overflows during insertion.
The rules
A B-tree of order m allows each node up to m - 1 keys and m children, but — this is what separates it from a loosely-defined multi-way tree — every node except the root must hold at least ceil(m/2) - 1 keys. No node is allowed to be nearly empty, which keeps the tree from wasting the disk reads Lesson 1 was trying to save.
The rule that matters most for predictable performance: every leaf sits at exactly the same depth. Unlike Unit II's plain BST, a B-tree can never degrade into Lesson 5's chain shape — the structure itself forbids it.
Splitting instead of chaining
Insertion finds the correct leaf the same way search does, then inserts the key there in sorted position. If that leaf now holds more than m - 1 keys, it overflows, and a B-tree never lets that stand — it splits the node into two, sends the middle key up to the parent, and repeats the check one level higher.
That upward push is exactly what keeps every leaf at the same depth: the tree never grows by adding a leaf deeper down, only by pushing a key up, and in the rare case that push reaches the root, the whole tree gains one level all at once, uniformly.
/* Node [10 20 30 40] with order 4 (max 3 keys) has overflowed */
Before split: [10 20 30 40]
Split at the middle key (20):
[20]
/ \
[10] [30 40]
/* 20 moves up to the parent; the leaf becomes two half-full nodes */The B-tree ADT
Exactly like Unit II's BST ADT, a B-tree's interface stays search, insert, and delete — the caller never needs to know the order, the fill rules, or when a split happened underneath. That hiding is what lets a database index be a B-tree without every piece of application code that queries it knowing anything about tree structure at all.
Try it yourself
A B-tree of order 4 has a leaf holding [10, 20, 30] with parent key 40 to its right. Insert 25, then describe the split that follows.
Need a hint?
Order 4 allows at most 3 keys per node. Where does 25 belong in sorted order, and what happens once the leaf holds 4?
Check the worked solution
25 slots between 20 and 30, giving the leaf [10, 20, 25, 30] — four keys, one too many for order 4. It splits at the middle key, 25: [10, 20] stays as one node, [30] becomes another, and 25 moves up to join the parent's keys. The leaf that started this never ends up deeper than its sibling — both new leaves sit at the same level the original leaf did.
Quick check
What guarantees that every leaf in a B-tree sits at exactly the same depth?
Why this lesson exists
Syllabus mapping
B Trees · B Trees ADT
Maps to course outcomes CO1, CO4.