Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I know the term order of a B-tree. Recently I heard a new term B tree with minimum degree of 2.
We know the degree is related with a node but what is degree of a tree.
Is degree imposes any kind of a restriction on height of a B-tree?

share|cite|improve this question

A B-Tree node can contain more than one key values whereas a BST node contains only one. There are lower and upper bounds on the number of keys a node can contain. These bounds can be expressed in terms of a fixed integer t>=2 called the minimum degree of the B-tree.

  • Every node other than the root must have at least t-1 keys. Every internal node other than the root thus has at least t children.
  • Every node can contain at most 2t-1 keys. Therefore, an internal node can have at most 2t children. We say that a node is full if it contains exactly 2t-1 keys.

Please click This Link to have an excellent basic on B-Tree and This Link for a follow up and most easily written algorithm of B-Tree operations.

share|cite|improve this answer

I don't think that degree of a tree is a standard term in either graph theory nor data structures. A degree is usually a property of a node/vertex of a graph, which denotes the number of its incident edges. For trees you sometimes consider only the edges to the children.

I suppose "B-tree with minimum degree of 2" means that every node has at least two children. In other words it is a lower bound for the number of children. On the other hand the order of a B-tree denotes the maximal node degree, and is therefore an upper bound.

share|cite|improve this answer

Order(m) of B-tree defines (max and min) no. of children for a particular node.

Degree(t) of B-tree defines (max and min) no. of keys for a particular node. Degree is defined as minimum degree of B-tree.

A B-tree of order m : All internal nodes except the root have at most m nonempty children and at least ⌈m/2⌉ nonempty children.

A B-tree of (minimum) degree t :

  1. each node has at most 2t-1 keys
  2. if node is not root, it has at least t-1 keys.
share|cite|improve this answer
Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. – FrankW Jun 30 '14 at 13:13

B-tree of order 5 OR m=5

max children = 5

min children = ceil(m/2) = 3

B-tree of degree 5 OR t=5

max keys = 2t-1

min keys = t-1

share|cite|improve this answer
Please don't just write a list of equations. Explain your answer so it's helpful to the person who asked the question. – David Richerby Dec 15 '13 at 18:58

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.