B-trees are tree data structures that are most commonly found in databases and filesystem implementations. B-trees keep data sorted and allow amortized logarithmic time insertions and deletions. Conceptually speaking B-trees grow from the bottom up as elements are inserted, whereas most binary trees generally grow down.
The idea behind B-trees is that inner nodes can have a variable number of child nodes within some pre-defined range. This causes B-trees to not need re-balancing frequently, unlike AVL trees. The lower and upper bounds on the number of child nodes are fixed for a particular implementation. For example, in a 2-3 B-tree (often simply 2-3 tree), each internal node may have only 2 or 3 child nodes. A node is considered to be in an illegal state if it has an invalid number of child nodes.
The "B" stands for "balanced" because all the leaf nodes appear at the same level in the tree.
