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

Updated 13 Nov 20265 min read
B-Trees and B+ Trees: Structure, Splits and Insertion

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

10

Root leaf [10]

20

Root leaf [10,20]

5

Root leaf [5,10,20]

6

Root [10]; children [5,6], [20]

12

Root [10]; children [5,6], [12,20]

30

Root [10]; children [5,6], [12,20,30]

7

Root [10]; children [5,6,7], [12,20,30]

17

Root [10,20]; children [5,6,7], [12,17], [30]

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.

Four panels tracing an order-4 B-tree over keys 10, 20, 5, 6, 12, 30, 7, 17, with 10 and later 20 moving up to become root keys.

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

10

Leaf [10]

20

Leaf [10,20]

5

Leaf [5,10,20]

6

Root [10]; leaves [5,6] -> [10,20]

12

Root [10]; leaves [5,6] -> [10,12,20]

30

Root [10,20]; leaves [5,6] -> [10,12] -> [20,30]

7

Root [10,20]; leaves [5,6,7] -> [10,12] -> [20,30]

17

Root [10,20]; leaves [5,6,7] -> [10,12,17] -> [20,30]

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.

Final B-tree and B+ tree for the same eight keys: 10 and 20 moved up on the left, duplicated on the right, with range 7 to 20 listed.

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] before 6. A B+ root appears when 6 causes overflow: the leaf splits into [5,6] and [10,20], and 10 is copied. Finally, 20 is root-only in the B-tree but appears in the B+ root and leaf [20,30].

Four traps change the answer completely:

  1. Treating m as maximum keys when the question defines it as maximum children.

  2. Moving a B+ separator out of its leaf instead of copying it.

  3. Allowing leaves to finish at different depths.

  4. 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.