B-tree

A B-tree generalizes a BST to multi-way nodes: each node stores many sorted keys and has one more child pointer than keys. That wide fan-out keeps trees shallow, so searching on disk or flash touches far fewer blocks than a binary tree—exactly what databases and file systems need.

Binary BST material (Binary search tree) explains ordering; B-trees apply the same comparison idea with ranges between keys. For pure in-memory structures you might still prefer AVL/red-black—see AVL and Red-black tree.

1) Node shape

In a B-tree of (maximum) order m, each internal node holds up to m−1 keys and up to m child pointers. Keys in a node are sorted; subtrees between keys carry values strictly in those ranges—parallel to BST left/right, but with many branches.

2) Typical invariants (overview)

• All leaves appear at the same depth (balanced multi-way tree).
• Every node except the root must be at least half full (standard B-tree)—exact lower bounds depend on how m is defined in your textbook.
• Root has at least two children if it is internal (unless it is a leaf).

3) Insert and delete

Insert: find the leaf position; if the node overflows after insertion, split it at the median key and push one key into the parent (possibly cascading splits up to the root).

Delete: remove from a leaf or replace with predecessor/successor; if a node becomes too empty, borrow from a sibling or merge nodes—possibly cascading merges.

4) Why disks love B-trees

One random disk read costs orders of magnitude more than CPU work on a few keys inside a block. Packing hundreds of keys per node amortizes that cost: tree height becomes O(log_m n), and with large m tied to block size, depth stays very small.

5) B-tree vs B+ tree

In a classic B-tree, data records may live in internal nodes or leaves depending on variant. A B+ tree keeps all keys in sorted order at the leaves and uses internal nodes only as indexes—better for range scans. See B+ tree.