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 8.12, some search key values appear twice.

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

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

2. Advantages:
   • Lack of redundant storage.
   • 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.