B-Tree Index Files

1. B-tree indices are similar to B -tree indices.
   • Difference is that B-tree eliminates the redundant storage of search key values.
   • In B -tree of Figure 11.11, some search key values appear twice.

   • A corresponding B-tree of Figure 11.18 allows search key values to appear only once.
   • Thus we can store the index in less space.

    
   Figure 11.8:   Leaf and nonleaf node of a B-tree.
   

2. Advantages:
   • Lack of redundant storage (but only marginally different).
   • Some searches are faster (key may be in non-leaf node).
3. Disadvantages:
   • Leaf and non-leaf nodes are of different size (complicates storage)
   • Deletion may occur in a non-leaf node (more complicated)
   Generally, the structural simplicity of B -tree is preferred.