indexing many large-scale computing applications are centered around data sets that are too large to fit into main memory the classic example is large database of records with multiple search keysrequiring the ability to insertdeleteand search for records hashing provides outstanding performance for such situationsbut only in the limited case in which all searches are of the form "find the record with key value unfortunatelymany applications require more general search capabilities one example is range query search for all records whose key lies within some range other queries might involve visiting all records in order of their key valueor finding the record with the greatest key value hash tables are not organized to support any of these queries efficiently this introduces file structures used to organize large collection of records stored on disk such file structures support efficient insertiondeletionand search operationsfor exact-match queriesrange queriesand largest/smallest key value searches before discussing such file structureswe must become familiar with some basic file-processing terminology an entry-sequenced file stores records in the order that they were added to the file entry-sequenced files are the disk-based equivalent to an unsorted list and so do not support efficient search the natural solution is to sort the records by order of the search key howevera typical databasesuch as collection of employee or customer records maintained by businessmight contain multiple search keys to answer question about particular customer might require search on the name of the customer businesses often wish to sort and output the records by zip code order for bulk mailing government paperwork might require the ability to search by social security number thusthere might not be single "correctorder in which to store the records indexing is the process of associating key with the location of corresponding data record section discussed the concept of key sortin which an index