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
RGB Model The RGB model is based on the assumption that any desired shade of colour can be obtained by mixing the correct amounts of red, green, and blue light. The exact hues

Q. Suggest a method of implementing two stacks in one array such that as long as space is there in an array, you should be capable to add an element in either stack. Using proposed

Q. Write down an algorithm to delete the specific node from binary search tree. Trace the algorithm to delete a node (10) from the following given tree. Ans. Algor


Q.1 What is an algorithm? What are the characteristics of a good algorithm? Q.2 How do you find the complexity of an algorithm? What is the relation between the time and space c

Define the term counting - Pseudocode Counting in 1s is quite simple; use of statement count = count + 1 would enable counting to be done (for example in controlling a repeat

Asymptotic notation Let us describe a few functions in terms of above asymptotic notation. Example: f(n) = 3n 3 + 2n 2 + 4n + 3 = 3n 3 + 2n 2 + O (n), as 4n + 3 is of

for i=1 to n if a[i}>7 for j=2 to n a[j]=a{j}+j for n=2 to n a[k]=a[j]+i else if a[1]>4 && a[1] for 2 to a[1] a[j]= a{j]+5 else for 2to n a[j]=a[j]+i ..

To delete an element in the list at the end, we can delete it without any difficult. But, assume if we desire to delete the element at the straining or middle of the list, then, we