B-Trees and B+ Trees: Structure, Splits and Insertion
Trace the same eight keys through an order-4 B-tree and B+ tree. The worked states show exactly when a key moves, when it is copied and how the final trees differ.
KnowledgeGate Team
Exam prep & CS education

B-trees and B+ trees are easy to mix up because both stay balanced and split full nodes. The decisive difference is where searchable data entries live: a B-tree can keep them in internal nodes, while a B+ tree keeps them at the leaf level and copies separator keys into internal nodes. Under one fixed order convention, the same sequence produces different B-tree and B+ tree structures.
B-tree and B+ tree rules, with order fixed first
A search tree of order m here has at most m child pointers, so an internal node has at most m - 1 keys. For order 4, every node holds at most 3 keys. Except for the root, a B-tree node has at least ceil(4/2) - 1 = 1 key. A non-leaf internal node has 2 to 4 children. A non-empty root has at least 1 key, and every leaf is at the same depth.
The B+ tree uses the same internal-node limits. Separately, each leaf holds at most 3 data keys. A four-key overflow splits into two leaves containing 2 keys each. Leaves are linked from left to right, internal separators guide searches, and the actual data-key entries remain in the leaves.
Books may define order as maximum keys or use minimum degree t. Translate the definition you are given before applying a memorised formula. The CS Fundamentals hub places this structure inside the wider foundation.
The split rule that separates B-trees from B+ trees
Both structures follow the same loop: search towards the target leaf, insert in sorted order, detect or prevent overflow, split the node, update its parent, and repeat upwards if needed. A root split creates a new root and increases height uniformly, so all old leaves remain at the same depth.
The promotion step is different. In the order-4 B-tree procedure used below, a full node containing [5, 10, 20] is split before descent. Median 10 moves up into the parent, or into a new root when the full node was the root, leaving [5] and [20]. It no longer remains in either child.
In the B+ procedure, inserting 6 first overflows [5, 10, 20] into [5, 6, 10, 20]. The leaf then splits into [5, 6] and [10, 20], and the smallest key of the right leaf, 10, is copied into the parent. The data entry for 10 stays in the right leaf.
These are declared classroom procedures: top-down pre-splitting for the B-tree and post-overflow leaf splitting for the B+ tree. If a question specifies another convention, that convention controls the result.
Worked B-tree insertion: all eight keys
Insert 10, 20, 5, 6, 12, 30, 7, 17 into an order-4 B-tree. Each row shows the state after one insertion; a semicolon separates the root from its children.
Inserted | State after insertion |
|---|---|
| Root leaf |
| Root leaf |
| Root leaf |
| Root |
| Root |
| Root |
| Root |
| Root |
Before inserting 6, split full root [5,10,20]: move 10 to a new root over [5] and [20], then insert 6 into the left child.
Before inserting 17, split full target [12,20,30]: move 20 to the root, then insert 17 into [12]. The final root [10,20] has leaves [5,6,7], [12,17] and [30].
Search 17 at root [10,20], take the middle child, and find it in [12,17]. Internal keys 10 and 20 are searchable and absent from the leaves.

Worked B+ tree insertion with the same keys
Now use the same sequence and a leaf capacity of 3. The complete state after each insertion includes leaf links, shown by arrows.
Inserted | State after insertion |
|---|---|
| Leaf |
| Leaf |
| Leaf |
| Root |
| Root |
| Root |
| Root |
| Root |
Inserting 6 creates overflow [5,6,10,20]. Split it into [5,6] and [10,20], copy 10 to a new root, and link the leaves. Inserting 30 creates [10,12,20,30]; split into [10,12] and [20,30], then copy 20 up.
For inclusive range [7,20], use separator 10 to reach [5,6,7] and start at 7. Follow the links, emit 7, 10, 12, 17, 20, and stop before 30. Root 10 and 20 are navigation copies; data entries remain in leaves.

Point search, range search and stored entries compared
Feature | B-tree | B+ tree |
|---|---|---|
Data entries | Internal nodes and leaves | Leaves only |
Separators repeat in leaves? | No | Yes |
Point search stops | Internal node or leaf | Data entry in leaf |
Range traversal | Ordered traversal | Follow leaf links |
Leaf split | Median moves up | Right-leaf minimum is copied up |
For 20, the B-tree search may stop at the root; the B+ search continues to [20,30]. Range [7,20] follows B+ leaf links, while this B-tree needs an ordered traversal.
Neither is always faster. I/O depends on height, capacity, layout, caching and the query. For split mechanics, use the side-by-side trace above; B+ Trees and Database Indexing: Worked Insert Example connects B+ trees to dense and sparse indexes, fanout, and disk I/O. Treat Hashing and Collision Resolution as a contrasting file-organisation technique, not proof that hashing always wins point lookups.
How insertion questions test the convention
Questions may ask you to derive key limits from an order definition, trace an insertion, name the promoted or copied separator, draw the final tree, count splits or height changes, follow a point search, or produce a range result.
Rapid check: A new B-tree root comes from splitting
[5,10,20]before6. A B+ root appears when6causes overflow: the leaf splits into[5,6]and[10,20], and10is copied. Finally,20is root-only in the B-tree but appears in the B+ root and leaf[20,30].
Four traps change the answer completely:
Treating
mas maximum keys when the question defines it as maximum children.Moving a B+ separator out of its leaf instead of copying it.
Allowing leaves to finish at different depths.
Forgetting to propagate an internal split upwards.
The short version and the next deliberate step
Declare the order convention, descend in sorted order, split at the stated capacity, move the median in a B-tree, copy the right-leaf minimum in this B+ convention, and propagate until the root is valid. Redraw both final trees from the blank sequence before checking the diagrams. Use Zero to Hero Complete CS Course for a broad CS path or CS Fundamentals for Placements by Sanchit Sir for placement-focused revision.
Keep learning
B-Tree and B+ Tree MCQs: 12 Solved Structure and Insertion Questions
Solve 12 B-tree and B+ tree questions from first principles. Each answer explains the governing invariant, byte inequality or insertion state.
Decision Trees: Calculate Information Gain and Prune Weak Branches
Build one classification tree by hand from ten machine rows, audit every candidate threshold, and see why validation can justify removing a perfectly pure training branch.
B+ Trees and Database Indexing: why indexes are fast, with a worked insert
B+ trees and database indexing explained: dense vs sparse, primary clustering and secondary indexes, B-tree vs B+ tree, with a worked B+ tree insert example.
Complete Binary Trees MCQs: 12 Solved Questions on Height, Leaves and Tree Properties
Work through 12 binary-tree MCQs, then use each explanation to separate rules for arbitrary, complete, full and perfect trees.





