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
(a) Suppose that t is a binary tree of integers (that is, an object of type BinTree of Int.) in the state shown in Figure 3.   Give the vectors returned by each of the f

In order to get the contents of a Binary search tree in ascending order, one has to traverse it in In-order

Adjacency list representation An Adjacency list representation of Graph G = {V, E} contains an array of adjacency lists mentioned by adj of V list. For each of the vertex u?V,

a. Explain the sum of subset problem. Apply backtracking to solve the following instance of sum of subset problem: w= (3, 4, 5, 6} and d = 13. Briefly define the method using a sta

INSERT FUNCTION /*prototypes of insert & find functions */ list * insert_list(list *); list * find(list *, int); /*definition of  anyinsert function */ list * inser

write an algorithm to delete an element x from binary search with time complex

Explain Backtracking The  principal idea is to construct solutions single component  at a time  and evaluate such  partially constructed candidates as follows. If a partiall

Draw trace table and determine output from the following flowchart using following data: Number = 45, -2, 20.5

Sorting is significant application activity. Several sorting algorithms are obtainable. But, each is efficient for a specific situation or a specific kind of data. The choice of a

Q. Give the adjacency matrix for the graph drawn below:                                                 Ans: Adjacency matrix for the graph given to us