B-TreeThe B-tree is a generalization of a binary search tree in that a node can have more than two children.
B-tree of order m is a tree which satisfies the following properties:
1. The root has atleast two child.
2. Every node has at most m children.
3. Every non-leaf node (except root) has at least [m/2] children.
4. A non-leaf node with k children contains k−1 keys.
5. All leaves appear in the same level, and carry information.
height of a B-treeLet n = the number of keys in T, n>=1, t>=2,
h = height of T. Then,
Let T be of height h. The number of nodes is minimized when root has 1 key and all other nodes have t–1 keys.
This gives us 2t^(i-1) nodes at depth i, 1<=i<=h, and 1 node at depth 0. Hence,
Operations on B-trees1. B-TREE CREATE