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

Ask an Expert

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

Write your message here..

Related Questions

General, whats the definition of ADT and data type? whats the definition of ADT and data type?

B-tree, Draw a B-tree of order 3 for the following sequence of keys: 2,4,9,... Draw a B-tree of order 3 for the following sequence of keys: 2,4,9,8,7,6,3,1,5,10.and delete 8 and 10

Searhing and sorting algorithms, how I can easily implement the bubble,sele... how I can easily implement the bubble,selection,linear,binary searth algorithms?

Breadth-first search , 1. Apply the variant Breadth-First Search algorithm ... 1. Apply the variant Breadth-First Search algorithm as shown in Figure 2 to the attached graph. This variant is used for computing the shortest distance to each vertex from the sta

State the ruby programming language, The Ruby Programming Language Alth... The Ruby Programming Language Although data structures and algorithms we study aren't tied to any program or programming language, we need to write particular programs in speci

Test whether a binary tree is a binary search tree, Q. Write down an algori... Q. Write down an algorithm to test whether a Binary Tree is a Binary Search Tree.              A n s . The algorithm to check whether a Binary tree is as Binary Search

The complexity ladder, The complexity Ladder: T(n) = O(1). It is ca... The complexity Ladder: T(n) = O(1). It is called constant growth. T(n) does not raise at all as a function of n, it is a constant. For illustration, array access has this c

Memory mapping, lower triangular matrix and upper triangular matrix lower triangular matrix and upper triangular matrix

Advanced data structures - splay trees, This is a unit of which targeted on... This is a unit of which targeted on the emerging data structures. Red- Black trees, Splay trees, AA-trees & Treaps are introduced. The learner must explore the possibilities of app

Define big oh notation, Big oh notation (O) : The upper bound for the funct... Big oh notation (O) : The upper bound for the function 'f' is given by the big oh notation (O). Considering 'g' to be a function from the non-negative integers to the positive real