B-Tree Visualization: Insert Your Own Keys

Press + and pick a key from 0 to 99 on the slider, or press Random for a new tree. The insertion plays step by step: the key going down from the root to its leaf, the key taking its place, and every split that sends a middle key up. Here you can insert keys; deleting them, with the borrowing and merging that follow, is explained step by step in the VisiGrab app.

386785102750516568758690

Byte I inserted 52 and the tree grew a new level. At the top, not at the bottom.

Neo That’s how a B-tree keeps every leaf on one level. Deleting keys, with every borrow and merge, is in the app.

App StoreGoogle Play
QR code for VisiGrab on your phone
Scan to install

Neo and Byte are the hosts of our YouTube series — made entirely of pixels.

How to use this B-tree visualizer

Press + and pick a key on the slider, then step through the insertion with →. The key comes in a blue circle above the root. Each step takes it one level down, into the child that holds its range of values, and the circle stands over the gap where the key belongs. In the leaf the key takes its place, and the keys stay in ascending order.

With Auto on, ▶︎ inserts the key and plays the whole insertion by itself; ❚❚ pauses it, and switching Auto off gives back ← and →.

A node holds at most three keys here. When a fourth comes in, a warning mark appears over the node. Then an arrow shows its middle key going up into the parent, and the node breaks in two around it. The parent may now hold too many keys itself; when the root breaks, its middle key becomes the new root, and the tree grows a level at the top. Levels draws and numbers the levels; this visualizer stops at 24 keys. History lists the keys in the order they went in, to download and load again later.

How does insertion in a B-tree work?

The new key goes down from the root, in each node into the child for its range of values, until it reaches a leaf, and takes its place there in order. If the leaf now holds more keys than a node may, it splits: its middle key moves up into the parent, and the keys on either side become two nodes. A split can make the parent too full in turn, so splits can climb all the way to the root. More in how a B-tree works.

Why are all the leaves on the same level?

A B-tree never grows at the bottom. A new key always goes into a leaf that is already there, and the tree gets taller only when the root splits and a new root appears above it, which adds one level to every path at once. So every leaf stays at the same depth, and finding a key never visits more nodes than the tree has levels.

What does maximum degree 4 mean?

A node's degree is its number of children, one more than its number of keys. With maximum degree 4, as here, a node holds at most three keys and has at most four children, and every node but the root holds at least one key. The first key offered here, 52, splits a leaf and then the root. In the app you can also choose a maximum degree of 5 or 6.

More tree visualizers: Binary search tree visualizer · AVL tree visualizer · Red-black tree visualizer