Info & Theory
A B-tree is a balanced multi-way search tree. Each node holds a sorted run of keys and pointers to children between them, so one node can have many descendants.
Order m rules
- A node has at most
mchildren. - A node holds at most
m−1keys. -
A non-root node holds at least
⌈m/2⌉−1keys. - All leaves are at the same depth.
Insert & split
Keys are inserted into the correct leaf. If a node overflows to
m keys, it splits: the median moves
up to the parent and the rest become two siblings. Splitting the
root grows the tree one level — from the top, never the bottom.
Why it stays balanced
Because the tree only grows by lifting a median upward, every
root-to-leaf path keeps the same length. Height grows like
log⌈m/2⌉(n), so even millions of keys
sit just a few levels deep.
Where it is used
B-trees and B+ trees back relational-database indexes and filesystems, where a shallow tree means few slow disk-page reads per lookup.
How this simulation works
This is a genuine B-tree, not a scripted animation. Pick an
order m between 3 and 6, then insert keys. Each key descends to
the correct leaf using the sorted keys in every node as signposts. When
a node fills to m keys it splits at the
median: the median key is promoted into the parent and the
remaining keys form two siblings. If the root itself splits, a fresh
root appears and the whole tree gains a level from the top, which is
why every leaf always stays at the same depth.
Reading the canvas
Each node is drawn as a box of sorted keys with child pointers dropping from the gaps between keys. The most recent split is highlighted so you can follow where the median went and how the two new sibling nodes were formed. The stats panel reports the live order, height, node count, total keys and the running split count. Try a small order such as 3 to trigger splits often, or use Random to fill the tree quickly.
Frequently asked questions
What is a B-tree?
A B-tree is a self-balancing multi-way search tree. Each node can hold many keys and many children, and all leaves stay at the same depth, so search, insert and delete are O(log n) with very few node visits — ideal for disk- and page-based storage.
What does the order m mean?
The order m is the maximum number of children a node may have. A node of order m holds at most m−1 keys and, when not the root, at least ceil(m/2)−1 keys. This simulation lets you choose m from 3 to 6.
How does a split work?
When a node would overflow with m keys, it splits: the median key is pushed up into the parent and the remaining keys become two sibling nodes. If the root splits, a new root is created and the tree grows one level taller from the top.
Why do all leaves stay at the same depth?
A B-tree only ever grows taller by splitting the root and pushing a key up. Because splits propagate upward and never lengthen one branch alone, every root-to-leaf path always has exactly the same length, keeping the tree perfectly height-balanced.
How is search performed in a B-tree?
Search scans the sorted keys inside a node to find the gap the target falls into, then follows the child pointer for that gap and repeats, descending one level per node until the key is found or a leaf is reached without it.
Why are B-trees used for database indexes?
Because each node packs many keys, the tree is very shallow, so a lookup touches only a handful of nodes — and therefore a handful of disk pages. This minimises slow disk reads, which is why B-trees and their B+ tree variant back almost every relational database index and many filesystems.
What is the difference between a B-tree and a B+ tree?
In a B-tree every node can store data values. In a B+ tree all values live in the leaves and internal nodes hold only routing keys, with the leaves linked in a list. That makes range scans easy, which is why most databases actually use B+ trees.
How tall does a B-tree get?
Height grows with the logarithm of the key count in base ceil(m/2). With a large order m a tree holding millions of keys may be only three or four levels deep, which is exactly why it is so efficient on disk.
What does the simulation highlight after a split?
The node that most recently split and the key pushed up into its parent are highlighted, so you can trace how the median moved and how the two sibling nodes were formed.
Is this a real B-tree implementation?
Yes. Insertion uses the standard split-on-overflow algorithm with median promotion. Keys are kept sorted in every node, all leaves remain at equal depth, and the order, height, node count and split count update live from the actual structure.