A B-tree is a self-balancing search tree that stores multiple sorted keys per node and allows nodes to have many children. Keeping many keys per node makes the tree shallow, so lookups, insertions, and deletions each touch only O(log n) nodes — ideal when each node is a disk or memory page.

How does a B-tree stay balanced on insert?

Insert always goes into a leaf. If a node exceeds its maximum number of keys it splits into two, and its median key moves up into the parent. Splits propagate upward; if the root splits, a new root is created and the whole tree grows one level taller — uniformly, so every leaf stays at the same depth.

Why do databases use B-trees?

Disk and SSD reads happen in pages, and a page holds many keys. A B-tree node maps to a page, so a tree of billions of keys is only three or four levels deep — a lookup is three or four page reads. That low height, plus keys staying sorted, is why B-trees (and B+ trees) underlie most relational database indexes and filesystems.

What is the difference between a B-tree and a B+ tree?

In a B+ tree all values live in the leaves and internal nodes hold only routing keys, and the leaves are linked in a list. That makes range scans and sequential reads very efficient, which is why most database indexes actually use B+ trees, a close variant of the B-tree shown here.

Algorithms · Data Structures

Watch a Node Overflow and Split.

How does a database index find one row among billions in three or four disk reads? A B-tree packs many sorted keys into each node and, when a node overflows, splits it in half and floats its median key up to the parent. The tree grows upward, never sideways — so every leaf stays the same depth and the tree stays shallow.

O(log n) search/insert · balanced · disk-friendly

many keys / node

Each node holds several sorted keys — here up to 3 — mapping to a disk page.

insert at a leaf

Every new key slots into a leaf, keeping the node's keys sorted.

split on overflow

A 4th key overflows: split in two, promote the median to the parent.

grow at the root

If the root splits, a new root appears — the whole tree deepens evenly.

btree.js — insert, overflow, split, promote

Ready

Insert keys one at a time into a B-tree with at most 3 keys per node. Press Step: each key drops into the correct leaf. When a leaf holds a 4th key it splits — the middle key rises to the parent, and if the root itself splits, the tree gains a level.

–

inserting

height

splits

How it works

A binary search tree makes one comparison per level and can grow tall and skinny. A B-tree does the opposite: it makes many comparisons per node and stays short. The magic that keeps it balanced is that the tree only ever grows at the top — splits push work upward, never leaving one branch longer than another.

Descend to a leaf

Follow the routing keys down: at each node, go into the child between the two keys that bracket your new key. Insertion always lands in a leaf.

Insert in sorted order

Slot the key into the leaf so the node's keys stay sorted. If the node now has ≤ 3 keys, you're done.

Overflow → split

A 4th key overflows. Split the node: left keeps the smaller keys, right takes the larger, and the median is promoted into the parent as a new routing key.

✓

Cascade or grow

The promotion may overflow the parent, splitting again up the chain. If the root splits, a fresh root holds the lone median — every leaf just got one level deeper, together.

O(log n)

Insert / delete

O(log n)

Height (n keys)

O(log_t n)

Node = page

1 disk read

The code

# MAX = 2t-1 keys per node; insert returns a promotion or None def insert(node, key): if node.leaf: sorted_put(node.keys, key) else: i = child_index(node, key) up = insert(node.child[i], key) if up: # child split — absorb its median node.keys.insert(i, up.median) node.child.insert(i + 1, up.right) if len(node.keys) > MAX: return split(node) # overflow → promote median up return None def split(node): mid = len(node.keys) // 2 right = Node(keys=node.keys[mid+1:], child=node.child[mid+1:]) median = node.keys[mid] node.keys, node.child = node.keys[:mid], node.child[:mid+1] return Promotion(median, right)

Because splits only ever add a node beside an existing one and push a single key upward, every leaf stays at the identical depth — that's the invariant that guarantees O(log n). Real databases tune the node size so one node fills one disk or memory page (often thousands of keys), which is why a B-tree over a billion rows is only three or four levels tall. The B+ tree variant keeps all values in linked leaves for fast range scans.

Quick check

1. When a node overflows, what happens to its median key?

2. Why does a B-tree stay balanced — all leaves at equal depth?

FAQ

What is a B-tree?

A balanced search tree with many sorted keys per node and many children, giving O(log n) search/insert/delete while staying only a few levels deep.

How does it stay balanced?

Inserts go into leaves; overflowing nodes split and promote their median upward. Height grows only when the root splits, so all leaves stay at equal depth.

Why do databases love B-trees?

A node maps to a disk/SSD page holding many keys, so even a billion-key index is 3–4 levels tall — a lookup is 3–4 page reads.

B-tree vs B+ tree?

A B+ tree keeps all values in linked leaves and uses internal nodes only for routing, which makes range scans fast. Most DB indexes use B+ trees.

Keep going

Finished this one? 0 / 62 Algorithms done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

Algorithms & DSA

Watch a Node Overflow and Split.

How it works

Descend to a leaf

Insert in sorted order

Overflow → split

Cascade or grow

The code

Quick check

FAQ

Keep going

Explore the topic

More Algorithms

Explore more from Vibe Engines

How it works

Descend to a leaf

Insert in sorted order

Overflow → split

Cascade or grow

The code

Quick check

FAQ

Keep going

Binary Search Trees →

AVL Trees →

Skip Lists →

Key-Value Store →

Explore the topic

More Algorithms

Explore more from Vibe Engines

Get the next one in your inbox.