I know the term order of a B-tree. Recently I heard a new term: B tree with minimum degree of 2.
We know that the degree is related to a node but what is the degree of a tree?
Does degree impose any kind of a restriction on the height of a B-tree?
$\begingroup$
$\endgroup$
asked Nov 21, 2012 at 5:17
Add a comment
|
7 Answers
$\begingroup$
$\endgroup$
2
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.
-
3$\begingroup$ Yeah. This was the point.
Degreerepresents the lower bound on the number of children. i.e the minimum number possible. Whereas theOrderrepresents the upper bound on the number of children. ie. the maximum number possible. Thanks. $\endgroup$– h8pathakOct 21, 2016 at 13:26 -
2$\begingroup$ Degree is absolutely a standard term in graph theory: the degree of a vertex is the number of edges incident on it. $\endgroup$ Oct 21, 2016 at 13:54
$\begingroup$
$\endgroup$
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-1keys. Every internal node other than the root thus has at leasttchildren. - Every node can contain at most
2t-1keys. Therefore, an internal node can have at most2tchildren. We say that a node is full if it contains exactly2t-1keys.
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.
$\begingroup$
$\endgroup$
I have seen three ways to characterize B-tree so far:
With degree of the B-tree $t$ (either minimum, as in CLRS Algorithms book, or maximum as in B-tree Visualizer).
The simplest B-tree occurs when $t=2$. Every internal node then has either 2, 3, or 4 children, and we have a 2-3-4 tree.
The text referenced in Nasir’s answer closely follows B-tree definition as given in Algorithms with detailed explanation of minimum degree properties.
With $L$ and $U$ parameters, with lower (upper) bound on number of children inner node is supposed to have (e.g. B-tree with $L=3, U=6$ is equivalent to B-tree with $t=3$ (both allowing of 2–5 keys per node),
With order of the B-tree $m$, given by Knuth in TAOCP, Vol. 3 such that any internal node has between $\left\lceil\frac{m}{2}\right\rceil$ and $m$ children.
To sum it up:
- With degree characterization the allowed number of children is bound to lie in $[t,2t]$ interval,
- while $L$ and $U$ allows for more precise specification of number of children (i.e. number of keys per node allowed).
With regard to second part of OP’s question there’s Theorem 18.1 in Algorithms:
If $n ≥ 1$, then for any $n$-key B-tree $T$ of height $h$ and minimum degree $t≥2$, $h≤\mathrm{log}_t\frac{n+1}{2}$.
$\begingroup$
$\endgroup$
1
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 :
- each node has at most 2t-1 keys
- if node is not root, it has at least t-1 keys.
-
$\begingroup$ 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. $\endgroup$– FrankWJun 30, 2014 at 13:13
$\begingroup$
$\endgroup$
2
Degree represents the lower bound on the number of children a node in the B Tree can have (except for the root). i.e the minimum number of children possible. Whereas the Order represents the upper bound on the number of children. ie. the maximum number possible.
B Tree properties with respect to the Order
NOTE: Wikipedia also states these
B Tree Properties with respect to the Degree
B Tree Properties with respect to Degree
NOTE: These can also be found in the CLRS book
-
2$\begingroup$ If you want to edit your answer, please use the edit link and don't repost. Also, please please don't use images as the main content of your post, since they're inaccessible to search engines and the visually impaired. If you are going to use an image, you need to cite its source. $\endgroup$ Oct 21, 2016 at 13:56
-
1$\begingroup$ Seconded, please transcribe your image into text. $\endgroup$– EvilOct 21, 2016 at 15:13
$\begingroup$
$\endgroup$
B-trees terminologies are not uniformly defined wherever I read, however the ambiguous question is what is the order of a B-Tree? and not much about degree of a B-Tree. Degree comes from the graph theory which states it as the sum of in degree and out degree of that node.
By which it can be inferred that degree is more closely related to number of pointers/child a B-Tree node can have instead of key values in the node.
According to Knuth and Michael J. Folk, a B-tree of order m is a tree with every node having at most m children. So very vaguely we can say that both are more or less equivalent terms in the context of B-Tree.
$\begingroup$
$\endgroup$
2
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
-
3$\begingroup$ Please don't just write a list of equations. Explain your answer so it's helpful to the person who asked the question. $\endgroup$ Dec 15, 2013 at 18:58
-
2