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
Gouraud Shading The faceted appearance of a Lambert shaded model is due to each polygon having only a single colour. To avoid this effect, it is necessary to vary the colour ac

CMY Model  The cyan, magenta, yellow (CMY) colour model is a subtractive model based on the colour absorption properties of paints and inks. As such it has become the standard

for (i = 0; i sequence of statements } Here, the loop executes n times. Thus, the sequence of statements also executes n times. Since we suppose the time complexity of th

a. Determine the result of inserting the keys 4,19, 17, 11, 3, 12, 8, 20, 22, 23, 13, 18, 14, 16, 1, 2, 24, 25, 26, 5 in order to an empty B-Tree of degree 3. Only draw the configu

Write an algorithm for multiplication of two sparse matrices using Linked Lists.

In the array implementation of the lists, we will use the array to hold the entries and a separate counter to keep track of the number of positions are occupied. A structure will b

For the Oscillating sort to be applied, it is necessary for the tapes to be readable in both directions and able to be quickly reversed. The oscillating sort is superior to the po

The two pointers per number of a doubly linked list prepare programming quite easy. Singly linked lists as like the lean sisters of doubly linked lists. We need SItem to consider t

QUESTION Explain the following data structures: (a) List (b) Stack (c) Queues Note : your explanation should consist of the definition, operations and examples.

What are the expression trees? Represent the below written expression using a tree. Give a relevant comment on the result that you get when this tree is traversed in Preorder,