How to compute depth of B-tree?

Question

If we know the number of keys being stored in a B-Tree, and the order of the B-Tree (ie. the maximum number of child pointers for the non-root nodes), is there a simple logarithmic equation to determine what the height of the tree will be?

Answer 1

Check out wikipedia:

Let m be the number of children per node, a B-tree of height h with all its nodes completely filled has n=mh−1 entries.

The best case height of a B-tree is:

ceil( log_m(n+1) )

Let d be the minimum number of children an internal (non-root) node can have. For an ordinary B-tree, d=⌈m/2⌉.

The worst case height of a B-tree is:

floor( log_d( (n+1)/2 ) + 1 )