File Organization: B-tree Index Files

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.

  1. 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.
  1. The root of the tree has at least two subtrees, unless it is itself a It forces the tree to branch early.
  2. 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:

  1. Key value appears only once in the node.
  2. Searching is faster than indexed sequential files.
  3. Performance is maintained r.t. growth of file size.

Disadvantages : The major disadvantages of B-tree index files are:

  1. Updation of records are more complicated then B+ trees.  
  2. Less efficient than B+ trees and direct files.
  3. 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)

Leave a Reply

Your email address will not be published. Required fields are marked *