A B-tree is a self-balancing search tree generalised from a binary search tree to allow more than two children per node. Each node holds between $t-1$ and $2t-1$ keys (where $t \geq 2$ is the minimum degree), sorted in order. A node with $k$ keys has $k+1$ child pointers. All leaves are at the same depth, so the tree is perfectly height-balanced, and the height is O(log n).

The key property is that a single node can hold many keys and pointers. By sizing nodes to match a disk block or memory page (typically 4 KB), a B-tree minimises I/O: one node read fetches hundreds of keys at once. This makes B-trees the standard index structure for databases and filesystems, where disk reads dominate cost. A Red-black tree minimises comparisons for in-memory data; a B-tree minimises I/O for on-disk data.

// B-tree node with minimum degree t=2 (2-3-4 tree)
// each node holds 1-3 keys and 2-4 children
[10 | 20 | 30]
 /     |     \   \
[5]  [15]  [25]  [35 40]

Search descends from the root, doing a linear or binary scan of each node's keys to find the correct child pointer, until the key is found or a leaf is reached. Insert descends to the appropriate leaf, inserts the key, and if the node overflows it splits into two nodes and promotes the median key to the parent. Splits propagate upward as needed, potentially creating a new root.

B-trees are used in SQLite, PostgreSQL, MySQL (InnoDB), NTFS, HFS+, and ext4 (for directory indices). The B+ tree is a variant where all data is stored in the leaves and internal nodes hold only keys, which is the more common choice for database indexes.