Visualize & Master
Algorithms & Data Structures
Explore classic & modern sorting algorithms, efficient searching techniques, and interactive data structure visualizations — all with real-time step-by-step animation, comparisons, swaps, and Big-O metrics.
About A B-Tree is a self-balancing search tree optimized for block storage (databases, filesystems)
A B-Tree is a self-balancing search tree optimized for block storage (databases, filesystems).
Each node holds many keys (up to m-1 for order m) and up to m children, so a tree with millions of keys stays only a few levels tall.
All leaves are kept at the same depth, and every node except the root holds at least ⌈m/2⌉-1 keys.
How It Works
Insertion searches down to a leaf, splitting any full node it must descend into — the median key moves up to the parent and the remaining keys divide into two nodes.
Splitting the root grows the tree upward (the only way height increases).
Because full nodes are split on the way down, a leaf never overflows during insertion.
Each node read or written maps to one disk block (page), so with order ~100 the height of a billion-key tree is only ~5 levels.
Search descends comparing against keys in each node to pick the child gap.
Time & Space Complexities
| Operation | Time | Space |
|---|---|---|
| Search | O(log_m n) | O(1) |
| Insert | O(log_m n) | O(log_m n) split chain |
| Delete | O(log_m n) | O(log_m n) |
| Node split | O(m) | O(m) |
| Height (m keys/node, n keys) | ≈ log_m n | — |
Best Use Cases
- Database indexes (MySQL InnoDB, PostgreSQL B-tree indexes)
- Filesystems (ext4, NTFS, HFS+ — directory and file metadata)
- Key-value stores and in-memory ordered structures
- Any workload with block-device I/O where fewer tree levels matter
Worked Example
Insert [5, 9, 3, 7, 1, 2, 8, 6, 0, 4] into an order-4 B-tree
Input: order 4 → max 3 keys per node; insert in order: 5, 9, 3, 7, 1, 2, 8, 6, 0, 4; then search 7- 1 Insert 5, 9, 3: they fill the root node [3, 5, 9].
- 2 Insert 7: the root is full, so it splits — the median 5 moves up to a new root, leaving [3] and [7, 9].
- 3 Continue inserting 1, 2, 8, 6: children split as they fill, pushing medians up.
- 4 Insert 0, 4: the leftmost child [1, 2, 3] is full, so it splits into [0, 1] and [3, 4], lifting 2 into the root.
- 5 The final root is [2, 5, 8] with children [0, 1], [3, 4], [6, 7], and [9].
- 6 Search 7: at the root, 2 < 7 < 8, descend into [6, 7] and find it. All leaves are at the same depth.
Pseudocode
function insert(tree, x):
if root is full: split root, height++
node = root
while node is not leaf:
child = node.children[index where x belongs]
if child is full:
split child (median up to node)
if x > node.keys[i]: child = child.rightSibling
node = child
insert x into leaf node at sorted position function split(parent, i):
child = parent.children[i]
median = child.keys[ceil(m/2)]
right = new Node(keys after median, children after)
child.keys = keys before median
parent.keys.insert(median) at position i
parent.children.insert(right) after child Insert Sequence
Full nodes split on the way down so every leaf stays at the same depth.