B-Trees

1)In a B-tree of order m,each internal node except the root and the leaves has ceiling(m/2) to m nodes.
2)the number is called the branching factor of the Tree.
3)Let n denote total number of keys,p total number  of nodes of B-Tree of branching factor(order) of m
then p=n/(m-1) since each nodes of T contains (m - 1)keys;
4)there are m^k nodes on level k;
so, (p total number  of nodes) = 1 + m^2 +m^3+m^4+.......+m^k;
5)p = (m^(k+1) - 1)/(m-1) = n/(m-1);
=>m^(k + 1) - 1 = n
=>m^(k + 1) = n+1
=>k = logm(n+1) - 1;

5)The use of  trees with high branching factors makes sense when we store the tree nodes on external memory devices with slow access times,such as disks and drums.