B-Trees | AlgoViz

B-TreesO(log n)

Best on a larger screen

AlgoViz's interactive walkthrough is built for a tablet or larger. Rotate your device or open it on a wider screen to explore the visualization.

Loading walkthrough.

SPEED

WalkthroughSTEP 0 / 0

Loading walkthrough.

Keyboard shortcuts

1search(node, key):

2 i = first slot where key <= node.keys[i]

3 if node.keys[i] == key: return found

4 if node is a leaf: return not found

5 return search(child[i], key)

6insert(key):

7 descend to the target leaf, comparing keys

8 add key to the leaf in sorted order

9 while a node holds order keys (overflow):

10 promote the median key to the parent

11 split the remaining keys into two nodes

12 if the root overflowed: grow a new root

Edit the input and run it through the same engine that drives the walkthrough.

order: 4
insert: 1 2 3 4 5 6 7 8 9 10 11 12 13
search: 6

Ask about this step or this algorithm.

Try: "Why a heap here?" or "What does this counter track?"