B-Tree Visualizer

How it works

1. Search: in each node, find the first key ≥ the target. Equal means found; otherwise follow the child pointer just left of that key. Reaching a leaf without it means the key is absent.
2. Insert: search down to the leaf where the key belongs and add it in sorted position.
3. If the leaf now has m keys, split it: the middle key moves up into the parent and the two halves become siblings.
4. A split can overflow the parent and repeat upwards; splitting the root creates a new root — the only way a B-tree grows taller.
5. Delete: remove the key from its leaf, or replace an internal key with its predecessor or successor from a leaf.
6. If a node drops below the minimum, borrow a key from a sibling through the parent or merge with a sibling; merges can shrink the tree at the root.

The rules of an order-m B-tree

• Every node holds at most m − 1 keys and has at most m children.
• Every node except the root holds at least ⌈m/2⌉ − 1 keys (so an internal node has at least ⌈m/2⌉ children). The root may hold a single key.
• Keys inside a node are sorted, and an internal node with k keys has exactly k + 1 children: child i holds the keys that fall between key i − 1 and key i.
• All leaves are on the same level, so the tree is perfectly height-balanced at all times.

With m = 3 every internal node has 2 or 3 children — a 2-3 tree; with m = 4 it has 2 to 4 — a 2-3-4 tree. Beware the second convention: CLRS describes B-trees by their minimum degree t, with t − 1 to 2t − 1 keys per node, so minimum degree t means order 2t. The visualizer lets you switch the order between 3 and 7 and rebuilds the same keys.

Why B-trees exist: the cost of a page read

Disks and SSDs read data in pages of a few kilobytes: fetching one byte costs as much as fetching the whole page, and a random page read is orders of magnitude slower than comparing keys in memory. A binary search tree over a billion keys is about 30 levels deep, so a lookup could mean 30 page reads.

A B-tree packs hundreds of keys into each node — one node per page. With a fan-out of a few hundred, a billion keys fit in about four levels, and the top levels usually stay cached in memory, so a lookup costs one or two actual reads. That is why B-trees and their variant, the B+ tree, are the standard index of relational databases (PostgreSQL, MySQL's InnoDB, SQLite, Oracle, SQL Server) and of file systems such as NTFS, HFS+, APFS, Btrfs and XFS.

Worked example: search and a split

The page opens on an order-3 tree (at most 2 keys per node) built by inserting 40, 20, 60, 10, 30, 50, 70, 5, 15, 25, 35, 45, 55, 65, 75: fifteen keys, four levels, every node holding a single key.

Searching for 55 reads [40] → [60] → [50] → [55] — four nodes, one per level. Now insert 36 and then 37. 36 joins the leaf [35], which has room for a second key: [35, 36]. 37 makes it [35, 36, 37] — one key too many — so the leaf splits: its median 36 moves up into the parent [30], which becomes [30, 36], and the leaf becomes [35] and [37]. The Learn panel's Insert and split step replays exactly this; try order 5 afterwards to see the same keys fit in fewer, wider nodes.

B-tree vs binary search tree vs AVL tree

• Keys per node: a BST or AVL node holds one key and two children; a B-tree node holds up to m − 1 keys and m children.
• Balance: a plain BST can degenerate to height n; an AVL tree keeps its height below about 1.44·log₂ n with rotations; a B-tree keeps every leaf at exactly the same depth by splitting and merging, with about log⌈m/2⌉ n levels.
• Work per node: a B-tree does more comparisons inside each node (a linear or binary search over its keys) but visits far fewer nodes — the right trade when visiting a node means a disk read, and still competitive in memory thanks to CPU caches.
• Growth: BSTs and AVL trees grow at the leaves; a B-tree grows at the root, which is exactly why its leaves always stay level.

B-tree vs B+ tree

In a classic B-tree, keys (and their records) live in internal nodes as well as leaves, and each key appears once. A B+ tree keeps all records in the leaves, stores only copies of keys in the internal nodes for routing, and links the leaves into a list. Internal nodes therefore hold more keys — a higher fan-out and a shallower tree — and a range scan just walks along the leaf chain. That is why nearly every database index is really a B+ tree. The ideas animated here — split on overflow, borrow or merge on underflow — carry over unchanged.

Time and space complexity

B-Tree 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 search(self, x, k):
        i = self.rank(x, k)
        if i < len(x.keys) and x.keys[i] == k:
            return x, i                         # found
        if x.leaf:
            return None                         # NOT FOUND
        return self.search(x.children[i], k)    # exactly one subtree can hold 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 Insertion & SplittingB-tree insertion step by step: find the leaf, insert in sorted order, split a full node around its median and push it up — even to a new root. Animated.
• 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.