Grid Structure

1. A grid structure for queries on two search keys is a 2-dimensional grid, or array, indexed by values for the search keys. Figure 8.11 (textbook 8.26) shows part of a grid structure for the deposit file.

    
   Figure 8.11:   Grid structure for file.
   

2. A particular entry in the array contains pointers to all records with the specified search key values.
   • No special computations need to be done
   • Only the right records are accessed
   • Can also be used for single search key queries (one column or row)
   • Easy to extend to queries on search keys - construct an -dimensional array.
   • Significant improvement in processing time for multiple-key queries.
   • Imposes space overhead.
   • Performance overhead on insertion and deletion.