In B-Tree index files, tree structure is used. A B-tree of order m is an m-way search tree with the following properties.
- Each node of the tree, except the root and leaves, has at least
subtrees and no more than n subtrees. It ensures that each node of tree is at least half full.
subtrees and no more than n - The root of the tree has at least two subtrees, unless it is itself a It forces the tree to branch early.
- All leaves of the tree are on the same It keeps the tree nearly balanced.
To overcome the performance degradation w.r.t. growth of files in index sequential files B-Tree index files are used. It is a kind of multilevel index file organisation. In tree structure, search starts from the root node and stops at leaf node.
(i) Non-Leaf Node :
In non-leaf node, there are two pointers. Pointer Pi points to any other node. Pointer Ri points to the block of actual records or storage area of records. Ki represents the key value.
(ii) Leaf Node :
In leaf node, there is only one pointer Pi which points to block of actual records or storage area of records. Ki represents the key value. A B-tree for file employee is shown in Figure 3.23.
Operations :
Searching a record : Searching a record with its key value starts from root node. It is possible to find desired record without going to leaf node in B-tree.
Deletion of a record : Deletion in B-tree is a complicated process. If desired entry is in leaf node, then, simply delete it otherwise find a proper replacement for that entry.
Insertion of a record : B-tree is a balanced tree and insertion of a new record in B-tree cause node splits and therefore affects the height of the tree.
Advantages : The major advantages of B-tree index files are:
- Key value appears only once in the node.
- Searching is faster than indexed sequential files.
- Performance is maintained r.t. growth of file size.
Disadvantages : The major disadvantages of B-tree index files are:
- Updation of records are more complicated then B+ trees.
- Less efficient than B+ trees and direct files.
- Searching time is still proportional to logarithm of the number of search keys.
Source: Gupta Satinder Bal, Mittal Aditya (2017), Introduction to Database Management System, 2nd Edition-University Science Press (2017)