B-Tree Is degree and order both are the same thing related to a B-Tree

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?

-

4 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.

-

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.

-

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

-
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