B-tree: insert, split and search

Exact tree state

Watch real splits and search decisions

This experiment builds a classic B-tree from your integer keys. Each node contains sorted keys and either no children or one more child than keys. Every leaf stays at the same depth. The green nodes identify the current comparison, insertion or split; blue nodes retain their existing contents. Edges represent actual parent-child relationships. The readable node inventory repeats every key and child identifier, so the picture is not the only way to follow the algorithm. A separate search trace follows comparisons through the completed tree and reports whether the requested key exists.

Build your own ordered input

Input keys accepts at most thirty-two comma-separated integers from minus 999 to 999. Order matters: entering the same set in another order can produce another valid shape. Duplicate keys are explicitly ignored, with a recorded explanation, because this fixture stores a set rather than duplicate records. Minimum degree t chooses two, three or four; a full node contains 2t minus one keys. Changing degree rebuilds the tree from the entered sequence instead of changing an invariant halfway through insertion. Apply input rebuilds after an edit. Invalid input displays an error and preserves the previous valid experiment. Empty input is a valid empty tree.

Reproduce the first root split

Load split example sets degree two, keys one through four and search key three. Advance with Next state until the full root containing one, two and three splits. The median two moves to a new root; one stays in the left leaf, and three moves into the right leaf. Inserting four then makes the right leaf contain three and four. This top-down algorithm splits a full child before descending into it, so a split snapshot is a valid tree even before the new key has been inserted. Try degree three with the same sequence: four keys fit in one node and no split is needed. Try a longer ascending sequence and inspect how the tree grows another level.

Inspect exact search and playback

Search key accepts one integer in the same range. Search completed tree rebuilds the entered input and jumps to the first search comparison. Search for three in the split example: the root directs the search right, where the key is found. Search for zero to follow the left branch and finish absent. Play maps all recorded states to sixty inspection seconds; Pause holds the state, Next state advances exactly one comparison or mutation, Restart rewinds, Speed changes viewing pace and Inspect time scrubs. Clear keys makes an empty tree; Restore defaults restores all inputs. The diagram has a keyboard-focusable, horizontally scrollable viewport for large trees, while the page itself remains phone-width. The readable inventory does not require horizontal scrolling.

Know what this tree does not model

This is a classic B-tree, not a B+ tree: keys can be found in internal nodes, and leaves are not linked. It stores integers without associated records. It implements insertion and lookup only, not deletion, merging, concurrent updates, disk pages, caching, transactions or recovery. Sixty seconds is a viewing duration, not database latency. Node identifiers are stable within one rebuild but may change with a new input order. Minimum degree bounds node occupancy; it is not a measured disk fan-out. Use the trace to reason about ordering, balance and search decisions, then consult the related articles for database-specific indexing behavior.