chap indexing file is created whose records consist of key/pointer pairs hereeach key is associated with pointer to complete record in the main database file the index file could be sorted or organized using tree structurethereby imposing logical order on the records without physically rearranging them one database might have several associated index fileseach supporting efficient access through different key field each record of database normally has unique identifiercalled the primary key for examplethe primary key for set of personnel records might be the social security number or id number for the individual unfortunatelythe id number is generally an inconvenient value on which to perform search because the searcher is unlikely to know it insteadthe searcher might know the desired employee' name alternativelythe searcher might be interested in finding all employees whose salary is in certain range if these are typical search requests to the databasethen the name and salary fields deserve separate indices howeverkey values in the name and salary indices are not likely to be unique key field such as salarywhere particular key value might be duplicated in multiple recordsis called secondary key most searches are performed using secondary key the secondary key index (or more simplysecondary indexwill associate secondary key value with the primary key of each record having that secondary key value at this pointthe full database might be searched directly for the record with that primary keyor there might be primary key index (or primary indexthat relates each primary key value with pointer to the actual record on disk in the latter caseonly the primary index provides the location of the actual record on diskwhile the secondary indices refer to the primary index indexing is an important technique for organizing large databasesand many indexing methods have been developed direct access through hashing is discussed in section simple list sorted by key value can also serve as an index to the record file indexing disk files by sorted lists are discussed in the following section unfortunatelya sorted list does not perform well for insert and delete operations third approach to indexing is the tree index trees are typically used to organize large databases that must support record insertiondeletionand key range searches section briefly describes isama tentative step toward solving the problem of storing large database that must support insertion and deletion of records its shortcomings help to illustrate the value of tree indexing techniques section introduces the basic issues related to tree indexing section introduces the - treea balanced tree structure that is simple form of the -tree covered in section -trees are the most widely used indexing method for large disk-based databasesand many variations have been invented section