B-Tree, step by step.

// how b-trees work

How a B-tree works

What is a B-tree?

A B-tree is a self-balancing multiway search tree. Each node stores several keys in sorted order, and an internal node with k keys has k + 1 children. Every leaf is at the same depth.

In the figure below, a node holds 20, 45 and 70. Its four children cover the keys below 20, between 20 and 45, between 45 and 70, and above 70. A child hangs from a gap, never from a key.

The B does not stand for binary. Its inventors, Rudolf Bayer and Edward McCreight (1970), never fixed its meaning.

B-tree order, maximum degree and minimum keys

The maximum degree m (Max. Degree) is the most children a node may have. A node holds at most one key fewer, so Max. Degree 4 means at most 3 keys per node. Every node except the root must also hold at least ⌈m/2⌉ − 1 keys; the root may hold just one.

Max. Degree	Max keys	Min keys	Min children (internal, non-root)	Minimum degree t
4	3	1	2	2
5	4	2	3	none
6	5	2	3	3

Knuth's order is the maximum number of children, as here; other texts use order for the minimum or maximum number of keys. CLRS uses a minimum degree t: a node holds t − 1 to 2t − 1 keys, so an odd Max. Degree such as 5 has no t. A B-tree of Max. Degree 4 is also called a 2-3-4 tree and corresponds to a red-black tree.

Searching a B-tree

In each node, the search finds the first key not smaller than the target. If that key is the target, the search ends; otherwise it descends through the gap before that key, or past the last key. Ending at a leaf without the target means the key is absent.

B-tree insertion and node splits

A new key always goes into a leaf: the insert walks down as in a search and adds it in order. A key already in the tree is refused.

If the leaf now holds one key too many (an overflow), it splits. Its middle key, the median, moves up into the parent; the keys left of it stay, and the keys right of it form a new node. With an even number of keys, the examples on this page send the right-hand middle up: an overfull node of 4 keys (Max. Degree 4) sends its third key up, leaving two keys left and one right. The left-hand middle is equally valid.

Splits can climb towards the root. When the root splits, a new root holding only the middle key appears above the two halves. This is the only way a B-tree grows taller. CLRS instead splits full nodes on the way down.

Below, 70 goes into a tree of Max. Degree 4 whose leaf and root are both full. The leaf splits, its middle key overfills the root, and the root splits too: the tree grows a level at the top. Step through it with the arrows.

A split that adds a level

All steps as text

1. This key will be added. Step forward to follow it down.
2. The key is bigger than every key in the root, so it goes down into its rightmost child.
3. A leaf makes room and takes the key, keeping its keys in ascending order.
4. This node holds one key too many.
5. The marked key is about to move.
6. The node breaks in two and sends its middle key up.
7. This node holds one key too many.
8. The node breaks in two and sends its middle key up.

B-tree deletion: borrow or merge

A key leaves only from a leaf. A key in an internal node first trades places with its in-order successor, the smallest key in the subtree to its right; the predecessor would work equally well.

A node other than the root may then be one key short of the minimum (an underflow). It is repaired with a neighbour: a child of the same parent directly left or right of it.

• Borrow (also called redistribution or rotation). A neighbour holding more than the minimum has a key to spare. The parent's separator drops into the short node, and the neighbour's spare, its nearest key, takes the separator's place. The left neighbour is checked first.
• Merge. Otherwise the short node joins a neighbour (the left one if it exists) and the separator from the parent. The parent loses a key and may become short, continuing the repair a level up.

In internal nodes, children move with the keys. If a merge takes the root's last key, the empty root is dropped and the merged node becomes the root. This is the only way a B-tree gets shorter.

Below, deleting 70 leaves its leaf empty. The left neighbour has a key to spare, so 60 comes down from the parent and 50 goes up to replace it. Nothing merges.

Borrowing from a neighbour

All steps as text

1. This key will be removed. Step forward to start.
2. The key is gone.
3. This node is one key short of the minimum.
4. The marked keys are about to move.
5. The short node takes the key from the parent, and the neighbour's spare goes up to replace it.

Here every node holds its minimum. Deleting 40 leaves a leaf short, no neighbour can spare a key, and two nodes merge. The merge leaves the parent short too, so a second merge follows a level up, and the tree loses a level.

A merge that removes a level

All steps as text

1. This key will be removed. Step forward to start.
2. The key is gone.
3. This node is one key short of the minimum.
4. No neighbour has a spare, so the two nodes are about to merge, with the key between them.
5. The two nodes and the key between them are now one node.
6. This node is one key short of the minimum.
7. No neighbour has a spare, so the two nodes are about to merge, with the key between them.
8. The two nodes and the key between them are now one node.

Why every B-tree leaf is at the same depth

Equal leaf depth is not the result of rebalancing; it follows from where the tree grows. New keys join existing leaves, and the height changes only at the root, so all root-to-leaf paths change together.

B-tree time complexity and height

Each operation follows one root-to-leaf path, with at most one split, borrow or merge per level, so its cost is proportional to the height. With n keys and t = ⌈m/2⌉, the fewest children of a non-root internal node, the tree has at most logt((n + 1) / 2) levels below the root. Space is linear: every node but the root holds its minimum.

Measure	Complexity
Search	O(log n)
Insert	O(log n)
Delete	O(log n)
Height	O(log n)
Space	O(n)

B-tree vs binary search tree

A plain binary search tree is O(log n) only when balanced; its worst case is O(n). Self-balancing binary search trees, such as the AVL tree and the red-black tree, keep their height at O(log n) by rebalancing after each insertion and deletion. A B-tree branches many ways per node instead of two, so a search visits far fewer nodes.

The figure below inserts the seven keys 10, 20, 30, 40, 50, 60 and 70, in ascending order, into both. In the BST each key becomes the right child of the previous one: a chain seven levels tall. The B-tree of Max. Degree 4 has two levels: 30 and 60 in the root, above the leaves [10 20], [40 50] and [70].

A B-tree cannot become a chain: it grows only at the root, and every non-root node keeps its minimum.

B-tree vs B+ tree, and where B-trees are used

Database indexes and file systems are built on B-trees, mostly the B+ tree variant. A B+ tree keeps records only in its leaves, copies of keys in the inner nodes, and links the leaves in order for range scans. A node fills one disk page and branches hundreds of ways, so three or four levels cover millions of keys.