Maximum depth of a B-tree

Question

How do you figure out the maximum depth of a B-tree?

Say you had a B-tree of order 1625, meaning each node has 1625 pointers and 1624 elements.

What is the maximum depth of the tree if it contains 85,000,000 keys?

Answer 1

Maximum depth depends on the algorithms used to manipulate the tree, and what their worse-case behavior is (I don't know the specifics, sorry). The approximate depth is log(N)/log(1625), assuming perfect balancing.

A B+-tree might be slightly deeper because only the leaves hold keys, but the difference is probably negligible. It also might be shallower if you consider that each non-leaf node only has to hold pointers.

Answer 2

The worst case height for a B-Tree of order m is log_m/2n.

See: http://en.wikipedia.org/wiki/B-tree#Best_case_and_worst_case_heights

Answer 3

Assuming

• the understanding of the order defined in the question
  Specifically that we can count on having 1625 pointers per node (some meanings of order define it as the maximum number of keys or pointers, which would then potentially increase the tree size computed below)
• the fact the leaf nodes will too store 1625 records (or pointers to these records)

... this tree would have a minimum depth of 3, i.e. it would have a root node, one layer of non-leaf nodes, and the layer of leaf nodes. ... this tree would have a maximum depth of 3 as well.

To compute the depth in the most optimal case:

• take the total number of records, 85,000,000, divide by the order, 1,625
  this gives the count of leaf-rows : 52,308
• take this number of leaf-rows, divide by the order
  this gives 33; this number is less than the order then we can stop diving, this is the number of pointers in the root node. Had this number been more than what one node can hold we'd have an extra level and would continue dividing.

We made two divisions so the tree depth is 3.

The worse case would happen if all nodes had had to be split, hence holding on average the order/2 (no rounding) pointers. The calculation for the worse case is similar, we just divide by order / 2 , i.e. 812.5 in our case, producing 104,616 leaf-nodes, 129 non-leaf nodes at the level above the leaves, and finally one root to keep track of these 129 non-leaf nodes.