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
Explain the term totalling To add up a series numbers the subsequent type of statement must be used: Total = total + number  This literally means (new) total = (old) t

Explain the representations of graph. The different ways of representing a graph is: Adjacency list representation : This representation of graph having of an array Adj of

Q. Which sorting algorithm can be easily adaptable for singly linked lists? Explain your answer as well.        Ans: The simple Insertion sort is sim

Determine the importance of array Arrays are significant since they allow many values to be stored in a single data structure whereas providing very fast access to each value.

Let G=(V,E) be a graph for which all nodes have degree 5 and where G is 5-edge is connected. a) Show that the vector x which is indexed by the edges E and for which xe = 1/5 for

How sparse matrix stored in the memory of a computer?

Binary Search Tree let three types of traversals by its nodes. They are: Pre Order Traversal In Order Traversal Post Order Traversal In Pre Order Traversal, we ca

prove that n/100=omega(n)

Warnock's Algorithm A divide and conquer algorithm Warnock (PolyList PL, ViewPort VP) If (PL simple in VP) then Draw PL in VP, else Split VP vertically and horiz

In the last subsection, we have implemented a stack by using an array. While a stack is implemented by using arrays, it suffers from the basic restriction of an array - i.e., its s