B-Tree:     We have already defined m-way tree introduction. A B-tree is a balanced M-way tree. A node of the tree may contain many records or key and pointers to children.­­­­­--

            A B-tree is also known as the balanced sort tree. It finds its use in external sorting. It is not a binary tree. To reduce disk accesses, several conditions of the tree must be tree.

The height of the must be kept to a minimum.

There must be no empty sub-trees above the leaves of the tree.

The leave of the tree must all be on the same level; and

All nodes except the leaves must have at least some minimum number of children.

B-Tree of order M has following properties.

1.      Each node has a maximum of M children and a minimum of M\2 children or any no. from 2 to the maximum.

2.      Each node has one fewer keys than children with a maximum of M-1 keys.

3.      Keys are arranged in a defined order within the node. All keys in the sub tree to the key of a key are predecessors of the key and that on the right are successors of the key.

4.      When a new key is to be inserted into a full node, the is split into two nodes and the key with the median value is inserted in the parent node. In case the parent node is the root a new root is created.

5.      All leaves are on the same level i.e. there is no empty sub tree above the level of the leaves.

The order imposes a bound on the business of the tree.

While root and terminal nodes are special cases normal nodes have between M/2 and M children for example a normal node of tree of order 11 has at least 6 more than 11 children.

B-Tree Insertion

First the search for the place where the new record must be put is done. If the node can accommodate the new record insertion is simple. The record is added to the node with an appropriate pointer so that number of points remain one more that the number of records. If the node overflows because there is an upper mind on the size of a node splitting is required. The node is split into three parts. The middle record is passed upward and inserted into the parent, leaving two children behind where there we one before. Splitting may propagate up the tree because the parent into which a record to be split in its child node, may overflow. Therefore if may also split. If the root is required to be split a new root is created with just two children and the tree grows taller by one level.

B-Tree Deletion

            As in the insertion method the record to be deleted is first searched for.

            If the record is in terminal node, deletion is simple. The record along with an appropriate pointer is deleted.

            If the record is not in terminal node, it is replaced by a copy of its successor that is a record with a next, higher value. The successor of any record not at the lowest level will always be in a terminal node. Thus in all cases deletion involves removing a record from a terminal node.

            If on deleting the record, the new node size is not below the minimum, the deletion is over, if the new node size is lower than the minimum an underflow occurs.

            Redistribution is carried out if either of adjacent siblings contains more than the minimum numbers of records for redistribution the contents of the node which has less than minimum records and the separation record from parent are collected. The central record from this collection is written back to parent. The left and right halves are written back to the two siblings.

            In case the node with less than minimum number of records has no adjacent sibling that is more than minimally full. Concatenation is used. In this case the node is merged with its adjacent sibling and the separating record from its parent.

In B tree all the leaves have been connected to from a linked list of the keys in sequential order. The B* tree has two parts: the index part is the interior nodes, the sequence set is the leaves Nodes a through I form the index part; nodes j through y form the sequence set. The linked leaves are an excellent aspect of B* tree; the keys can be accessed efficiently both directly & sequentially.

B tree is used to provide indexed sequential file organization the key value in the sequence set are the key values in the record collection the key values in the index part exist solely for internal purposes of directing access to the sequence set. 

Data Structure & Algorithms Assignment Help, Live Experts 

Struggling with data structure problems? Data structure subject is quite tough to learn? Need quick assistance in data structure questions? ExpertsMind.com is right place for you where your search ends, We at ExpertsMind offer online data structure assignment help, data structure homework help and data structure and algorithms question's answers by best online support by qualified tutors.

ExpertsMind.com - B-Tree Assignment Help, B-Tree Homework Help, B-Tree Assignment Tutors, B-Tree Solutions, B-Tree Answers, Trees Assignment Tutors