Take the 2-minute tour ×
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.

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|improve this question
add comment

3 Answers

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|improve this answer
add comment

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|improve this answer
add comment

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|improve this answer
1  
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
add comment

Your Answer

 
discard

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.