B+ Tree Simulator

How B+ Tree Simulator works

A B+ tree keeps every key in sorted order across a shallow, wide tree designed for disk. Two rules distinguish it from a B-tree: all actual records live in the leaves, and internal nodes hold only separator keys used for routing. The leaves are also chained left to right, which is what makes range queries cheap — find the start, then walk the chain. Search descends from the root comparing against separators until it reaches a leaf, so every lookup costs exactly the height of the tree. Insertion finds the target leaf and adds the key in order; if that overflows the node beyond its capacity, the leaf splits in half and a copy of the middle key is pushed up as a new separator. Internal splits move the middle key up instead of copying it. Deletion removes from a leaf and, if the node falls below the minimum occupancy, borrows a key from a sibling or merges with one, propagating upward. Because the tree only grows at the root, every leaf stays at the same depth.

Pseudocode

search(key):
    node = root
    while node is internal:
        i = first index with key < node.keys[i]      // separators are routing only
        node = node.children[i]
    return node.find(key)                            // leaf holds the record

insert(key, value):
    leaf = descendToLeaf(key)
    leaf.insertSorted(key, value)
    if leaf.count <= maxKeys: return

    // leaf overflow: split and COPY the middle key up
    (left, right, sepKey) = splitLeaf(leaf)
    link left.next = right                           // keep the leaf chain intact
    insertIntoParent(left, sepKey, right)

insertIntoParent(left, sepKey, right):
    if left is root:
        root = new InternalNode(keys=[sepKey], children=[left, right])
        return
    parent = left.parent
    parent.insertSorted(sepKey, right)
    if parent.count > maxKeys:
        // internal overflow: split and MOVE the middle key up
        (l, r, up) = splitInternal(parent)
        insertIntoParent(l, up, r)

delete(key):
    leaf = descendToLeaf(key)
    leaf.remove(key)
    while node.count < minKeys and node is not root:
        if a sibling has a spare key: borrowFromSibling(node)
        else:                        mergeWithSibling(node)
        node = node.parent
    if root is internal and root.count == 0:
        root = root.onlyChild                        // tree shrinks by one level

Time and space complexity

Time

O(log_b n) for search, insert and delete

Space

O(n)

With branching factor b the height is log_b n — for b in the hundreds, which is typical when a node is one disk page, a few million records sit three or four levels deep, so a lookup costs three or four page reads.

Worked example

Order-4 B+ tree (max 3 keys per node). Insert 10, 20, 5, 30, 25 in that order.

1. Insert 10, 20, 5Single leaf, sorted: [5, 10, 20]. Full but not overflowing.
2. Insert 30Leaf would become [5, 10, 20, 30] — overflow. Split into [5, 10] and [20, 30]. Copy 20 up: root becomes internal node [20] with the two leaves as children, chained 5,10 → 20,30.
3. Insert 25Routing: 25 ≥ 20, so descend right. Leaf becomes [20, 25, 30]. No overflow.
4. Search 25At root, 25 ≥ 20 → right child. Scan leaf [20, 25, 30] → found. Two node visits.

Height-2 tree: root [20], leaves [5, 10] ⇄ [20, 25, 30]. Note 20 appears twice — once as a separator in the root and once as a real record in the leaf. That duplication is normal and required.

Common exam mistakes

• Confusing B+ tree splits with B-tree splits. A leaf split copies the middle key upward (it must stay in the leaf); an internal split moves it up (it must not stay).
• Expecting to find records in internal nodes. In a B+ tree every record is in a leaf — internal keys are routing separators only, and a search never terminates early.
• Forgetting to relink the leaf chain after a split or merge. The tree stays correct for point lookups but range scans silently skip records.
• Using the wrong comparison at the separator. A key equal to a separator goes right, not left, if the separator was copied up from the right-hand leaf.
• Letting the root sit below the minimum occupancy check. The root is exempt — it is allowed to hold a single key, and the tree only shrinks when the root ends up with no keys at all.

Frequently asked questions

Related simulators