chap indexing second level index linear indexdisk blocks figure simple two-level linear index the linear index is stored on disk the smallersecond-level index is stored in main memory each element in the second-level index stores the first key value in the corresponding disk block of the index file in this examplethe first disk block of the linear index stores keys in the range to and the second disk block stores keys in the range to thusthe first entry of the second-level index is key value (the first key in the first block of the linear index)while the second entry of the second-level index is key value jones aa ab ab smith ax ax zx zukowski zq ff figure two-dimensional linear index each row lists the primary keys associated with particular secondary key value in this examplethe secondary key is name the primary key is unique four-character code -entry table to find the greatest value less than or equal to the search key this directs the search to the proper block in the index filewhich is then read into memory at this pointa binary search within this block will produce pointer to the actual record in the database because the second-level index is stored in main memoryaccessing record by this method requires two disk readsone from the index file and one from the database file for the actual record every time record is inserted to or deleted from the databaseall associated secondary indices must be updated updates to linear index are expensivebecause the entire contents of the array might be shifted by one position another problem is that multiple records with the same secondary key each duplicate that key value within the index when the secondary key field has many duplicatessuch as when it has limited range ( field to indicate job category from among small number of possible job categories)this duplication might waste considerable space one improvement on the simple sorted array is two-dimensional array where each row corresponds to secondary key value row contains the primary keys