Other algorithms / interactive lesson
Build a balanced multi-way search tree step by step. Watch keys move through nodes, see full nodes split, and connect B-tree invariants to database indexes.
About the algorithm
A B-tree is a balanced multi-way search tree designed for storage systems. Instead of storing one key per node like a binary search tree, each node stores a sorted block of keys and many child pointers, which keeps the tree shallow even for huge datasets.
B-trees were introduced by Rudolf Bayer and Edward M. McCreight at Boeing Research Labs in 1970. Their goal was practical: keep indexes efficient when data lives on slower block devices, where reading one large page is much cheaper than following many tiny pointers.
For a minimum degree t, every node can hold up to 2t - 1 keys and up to 2t children. Keys inside a node are sorted. During insertion, a top-down implementation splits full nodes before descending into them, promotes the median key to the parent, and finally inserts the new key into a non-full leaf.
B-trees and closely related B+ trees are the backbone of database indexes, filesystems, key-value stores, and storage engines. They are useful whenever data is much larger than memory and the dominant cost is reading or writing disk, SSD, or page-sized blocks.
Code companion
Connect each visual decision to an implementation pattern.
insert(tree, value):
if root is full:
newRoot = empty internal node
newRoot.children[0] = root
splitChild(newRoot, 0)
root = newRoot
insertNonFull(root, value)
insertNonFull(node, value):
if node is a leaf:
insert value into node.keys in sorted order
return
childIndex = range that can contain value
if node.children[childIndex] is full:
splitChild(node, childIndex)
if value > promoted median:
childIndex = childIndex + 1
insertNonFull(node.children[childIndex], value)