Maximum depth of a B-tree

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 co开发者_Go百科ntains 85,000,000 keys?

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

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 dividing, 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.

B tree is a balanced , the worst case retrieval is bounded by its height.Each node in a Btree of capacity order has d. Maximum depth = worst case

d=1624/2=812

Height <= log_d+1 ((n+1)/2)+1

the answer is log₈₁₂₊₁ ((85,000,000+1)/2)+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.

The formula for max depth of a b tree has already been given by Can Berk Güder. In your case m = 1625

But having odd number of pointers and even number of keys may not be a good idea because in that case, you will have to unevenly split a node when it is full.

Rather you should keep odd number of keys and even number of pointers per node for uniform splitting of nodes.

This is for B+, not sure about B.

85,000,000 records, in best case, are recorded in ceiling(85m/1624)=52340 leaves. This is the bottom level, and it is why we are using number of elements rather than number of pointers.

To find how many levels there are, we'll keep dividing the leaf numbers we find to the order, taking the ceiling along the way: ceiling(52340/1625)=33. This time we are using the number of pointers, because we already determined the bottom level, where elements are stored, and now working with pointers to point to element leaves.

As this number is not greater than the order itself, we stop there, because this is the root; top level. Root has 33 pointers that can point to a max of 33x1625 (53625) leaves, the difference shouldn't confuse you as not all of the element leaves could be filled to the max. 53625 leaves can store at most, 53625x1624 (87,087,000) elements in them, which is more than enough to hold our example.

Back to the question, there is only the root, and the element leaves below it, so the depth is 2.

Hope this helps.