B-tree, Data Structure & Algorithms

Unlike a binary-tree, each node of a B-tree may have a number of keys and children. The keys are stored or saved in non-decreasing order. Each key has an related child that is the root of a subtree containing all nodes with keys less than or equal to the key but greater than the preceding key. A node also contains an additional rightmost child that is the root for a subtree containing all keys greater than any keys in the node.

A B-tree has a minimum number of permissible children for each node known as the minimization factor. If t is this minimization factor, then every node must have at least t - 1 keys. Under certain conditions, the root node is allowed to violate this property by having fewer than t - 1 keys. Every node can have at most 2t - 1 keys or, equivalently, 2t children.

For n greater than or equal to one, the height of an n-key b-tree T of height h with a smallest degree t greater than or equal to 2, h≤logt (n+1/2)

 

Posted Date: 7/10/2012 3:21:42 AM | Location : United States







Related Discussions:- B-tree, Assignment Help, Ask Question on B-tree, Get Answer, Expert's Help, B-tree Discussions

Write discussion on B-tree
Your posts are moderated
Related Questions
Create a class "box" that will contain a random integer value v such that O

Explain about Hidden-surface Hidden-line removal refers to wire-frame diagrams without surface rendering and polygonal surfaces with straight edges. Hidden-surface removal ref


N = number of rows of the graph D[i[j] = C[i][j] For k from 1 to n Do for i = 1 to n Do for j = 1 to n D[i[j]= minimum( d ij (k-1) ,d ik (k-1) +d kj (k-1)

Two-dimensional array is shown in memory in following two ways:  1.  Row major representation: To achieve this linear representation, the first row of the array is stored in th


/* the program accepts two polynomials as a input & prints the resultant polynomial because of the addition of input polynomials*/ #include void main() { int poly1[6][

Question 1 Write the different characteristics of an algorithm Question 2 Explain in brief the asymptotic notations Question 3 Write an algorithm of insertion sort and e

Read the scenario (Pickerings Properties). (a) List the functions of the system, as perceived by an external user. (b) List the external entities. Note that because we are mo

In this unit, we have learned how the stacks are implemented using arrays and using liked list. Also, the advantages and disadvantages of using these two schemes were discussed. Fo