B-tree is a self-balancing tree data structure that maintains sorted data. B-tree stores data such that each node contains keys in ascending order. Unlike a binary tree, each node in a B-Tree can have more than 2 children. Each node can have up to
m children, where
m is called the tree’s “order”.
Unlike self-balancing binary search trees, it is optimized for systems that read and write large blocks of data. It is most commonly used in database and file systems.
By maximizing the number of keys within each internal node, the height of the tree decreases and the number of expensive node accesses is reduced. In addition, rebalancing of the tree occurs less often. B-trees may waste some space, since nodes are not entirely full.