CODEWITHSUNDEEP
data-structuresb-tree
Govind Parmar
Govind Parmar

Reputation: 21532

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?

Upvotes: 1

Views: 2710

Answers (1)

Justin
Justin

Reputation: 4216

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 )

Upvotes: 2

Related Questions