Search code examples
data-structuresb-tree

How to compute depth of B-tree?

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?

Solution

  • 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 )