Search code examples
data-structurestreeb-tree

Maximum number of keys in a B-Tree

I use the following definition of a B-Tree (according to wikipedia: https://en.wikipedia.org/wiki/B-tree):

Each node contains from d to 2d Keys.

I am searching now for the formula, how to calculate the maximum number of keys in the B-Tree with height = h. How can I do this?

Btw: What is the meaning of d? Can I say it is the degree of the tree?

Solution

  • d is the B tree degree.

    Only internal nodes are constrained with d, the rule does not apply to the root. Since the root can have more keys than 2d - 1, I would say that maximum number of keys in the B tree is not limited.