B-Tree Insertion & Splitting

How it works

1. If the tree is empty, the key becomes a root that is also a leaf.
2. Walk down from the root: in each node, follow the child between the two keys that surround the new key. If the key is already there, stop.
3. Insert the key into the leaf, keeping its keys sorted.
4. While a node has m keys: take its median, move the keys after the median (and their children) into a new right sibling, and keep the keys before it.
5. Insert the median into the parent, with a pointer to the new right sibling just after it, and check the parent next.
6. If the node that split was the root, create a new root holding just the median, with the two halves as its children.

Worked example: three inserts, three outcomes

This page opens on an order-3 tree (at most 2 keys per node): root [40, 70]; below it [20], [55] and [85, 95]; and the leaves [10], [30], [50], [60, 65], [80], [90], [97, 99].

• Insert 25 — no split. 25 < 40 leads to [20], and 25 > 20 to the leaf [30]. The leaf has room, so it becomes [25, 30]. Most inserts end exactly like this.
• Insert 62 — one split. The walk goes 40 < 62 < 70 into [55], then right into [60, 65]. The leaf becomes [60, 62, 65] — one key too many. Its median 62 moves up into [55], which becomes [55, 62], and the leaf splits into [60] and [65].
• Insert 98 — splits all the way up. [97, 99] becomes [97, 98, 99]: 98 moves up into [85, 95], which becomes [85, 95, 98] and splits as well, sending 95 up into the root. The root [40, 70, 95] overflows too, so it splits and 70 becomes a brand-new root with [40] and [95] below it. The tree grew from three levels to four — and every leaf is still on the same level.

Run each case with the Insert cases buttons above; step mode pauses after every phase.

Why the median moves up

Splitting around the median gives two halves of (almost) equal size, each with at least ⌈m/2⌉ − 1 keys — exactly the minimum a non-root node needs, so both new nodes are legal. The median itself is larger than everything in the left half and smaller than everything in the right half, so in the parent it becomes the separator between the two new children and the search rule keeps working. For odd m the halves are equal; for even m one half gets an extra key — this visualizer keeps it on the left.

Bottom-up vs top-down splitting

The algorithm animated here is bottom-up: insert into the leaf first, then split on the way back up for as long as nodes overflow. It remembers the path (or uses parent pointers) and only ever splits when it has to.

CLRS presents a top-down, single-pass version instead: on the way down, any node that is already full (2t − 1 keys) is split before the search enters it, so there is always room for a key moving up and the algorithm never walks back. That suits concurrency and disk writes, but it sometimes splits nodes that would never have overflowed, and it relies on the maximum key count being odd. Both versions produce valid B-trees, though not always the same shape.

Inserting sorted keys

Sorted input is the worst case for a plain binary search tree, but a B-tree stays perfectly balanced: every new key lands in the rightmost leaf, which keeps splitting and pushing keys up the right edge. The price is space — each split leaves its left half at the minimum and never touches it again, so sorted inserts produce nodes that are only about half full.

Databases special-case this append pattern. When PostgreSQL splits the rightmost page of a level it leaves the left page nearly full instead of half full, and InnoDB fills pages about 15/16 full when keys arrive in order. Load the Sorted example (5, 10 … 80) to watch the right edge grow.

Common mistakes

• Splitting too early. A node may legitimately hold m − 1 keys; it splits only when an insert would give it m (or, top-down, before entering a node that is already full).
• Forgetting the children. When an internal node splits, the right half takes the children to the right of the median: k keys always come with k + 1 children.
• Inserting into an internal node. New keys always go into a leaf; keys reach internal nodes only by moving up during a split.
• Mixing up order and minimum degree. "Order 4" (at most 3 keys) and "minimum degree 2" (at most 3 keys) describe the same 2-3-4 tree, while "minimum degree 4" allows 7 keys per node.

Time and space complexity

B-Tree Insertion in Python

from bisect import bisect_left


class Node:
    def __init__(self, leaf=True):
        self.leaf = leaf
        self.keys = []      # sorted; at most m - 1 of them
        self.children = []  # len(keys) + 1 subtrees when internal


class BTree:
    def __init__(self, m):
        self.m = m                          # order: at most m children per node
        self.max_keys = m - 1
        self.min_keys = (m + 1) // 2 - 1    # ceil(m/2) - 1, for every node but the root
        self.root = Node()

    @staticmethod
    def rank(x, k):
        # i <- #keys in x below k: the child to follow / where k belongs
        return bisect_left(x.keys, k)

    def insert(self, k):
        if not self.root.keys:                  # empty tree: the root becomes leaf [k]
            self.root.keys.append(k)
            return
        x, path = self.root, []                 # path: (parent, child index) on the way down
        while True:                             # walk down
            i = self.rank(x, k)
            if i < len(x.keys) and x.keys[i] == k:
                return                          # already present
            if x.leaf:
                break
            path.append((x, i))
            x = x.children[i]
        x.keys.insert(i, k)                     # insert k into x at i
        while len(x.keys) > self.max_keys:      # overflow: split around the median
            mid = len(x.keys) // 2
            med = x.keys[mid]                   # the middle key moves up
            right = Node(x.leaf)
            right.keys = x.keys[mid + 1:]       # keys after med (+ their children)
            if not x.leaf:
                right.children = x.children[mid + 1:]
                x.children = x.children[:mid + 1]
            x.keys = x.keys[:mid]               # x keeps the keys before med
            if not path:                        # x is the root
                self.root = Node(leaf=False)
                self.root.keys = [med]
                self.root.children = [x, right]
                return                          # the tree grew one level taller
            p, j = path.pop()
            p.keys.insert(j, med)               # push med into the parent ...
            p.children.insert(j + 1, right)     # ... and link the new right node
            x = p                               # the parent may overflow now

The visualizer above shows the same code in Python, C++, Java and JavaScript.

Frequently asked questions

Keep learning

• B-Tree VisualizerB-tree visualizer: insert, search and delete keys in a B-tree of order 3 to 7, watch nodes split, borrow and merge, and see why databases are built on B-trees.
• B-Tree Deletion — Borrow & MergeB-tree deletion step by step: remove from a leaf or swap in the predecessor, then fix underflow by borrowing from a sibling or merging nodes. Animated.
• Binary Search Tree VisualizerBinary search tree visualizer: insert, search and delete keys step by step, see why every operation costs O(h), and compare a plain BST with AVL and B-trees.
• AVL Tree VisualizerAVL tree visualizer: insert and delete keys, watch heights and balance factors update and LL, RR, LR, RL rotations keep every operation O(log n).
• AVL Rotations — LL, RR, LR, RLAVL tree rotations explained: spot the LL, RR, LR and RL cases from balance factors and fix each with a single or double rotation — animated step by step.