Question 1

What is a B-tree?

Accepted Answer

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.

Question 2

What does the order m mean?

Accepted Answer

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.

Question 3

How does a split work?

Accepted Answer

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.

Question 4

Why do all leaves stay at the same depth?

Accepted Answer

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.

Question 5

How is search performed in a B-tree?

Accepted Answer

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.

Question 6

Why are B-trees used for database indexes?

Accepted Answer

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.

Question 7

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

Accepted Answer

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.

Question 8

How tall does a B-tree get?

Accepted Answer

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.

Question 9

What does the simulation highlight after a split?

Accepted Answer

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.

Question 10

Is this a real B-tree implementation?

Accepted Answer

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.

🗃️ B-Tree — Multi-Way Search Tree

About B-Tree Index Structure

What did you find?