B-Tree is a generalization of binary tree allowing > 2 children per node. It’s a multi-way tree. B-Tree allows search operation in O(log n). B-tree is usually a fat tree with height kept minimum. Every node can have more than one key and (number of keys +1) children. It’s widely used in databases and file systems as it’s optimized for reading/writing data from/to disk storage.
Properties of b-tree
- Order of a b-tree is defined by the max number of children a node can have. In the above figure, the order of b-tree is 5. Note the left most leaf node.
- Number of keys in a node is (number of children – 1)
- All leaf nodes in b-tree are at same level.
- Keys of a node are in sorted order. The child between two keys k1 and k2 contains all keys in range from k1 and k2.