chap indexing key value for each block in that cylindercalled the cylinder index when new records are insertedthey are placed in the correct cylinder' overflow area (in effecta cylinder acts as bucketif cylinder' overflow area fills completelythen system-wide overflow area is used search proceeds by determining the proper cylinder from the system-wide table kept in main memory the cylinder' block table is brought in from disk and consulted to determine the correct block if the record is found in that blockthen the search is complete otherwisethe cylinder' overflow area is searched if that is fulland the record is not foundthen the system-wide overflow is searched after initial construction of the databaseso long as no new records are inserted or deletedaccess is efficient because it requires only two disk fetches the first disk fetch recovers the block table for the desired cylinder the second disk fetch recovers the block thatunder good conditionscontains the record after many insertsthe overflow list becomes too longresulting in significant search time as the cylinder overflow area fills up under extreme conditionsmany searches might eventually lead to the system overflow area the "solutionto this problem is to periodically reorganize the entire database this means re-balancing the records among the cylinderssorting the records within each cylinderand updating both the system index table and the within-cylinder block table such reorganization was typical of database systems during the and would normally be done each night or weekly tree-based indexing linear indexing is efficient when the database is staticthat iswhen records are inserted and deleted rarely or never isam is adequate for limited number of updatesbut not for frequent changes because it has essentially two levels of indexingisam will also break down for truly large database where the number of cylinders is too great for the top-level index to fit in main memory in their most general formdatabase applications have the following characteristics large sets of records are frequently updated search is by one or combination of several keys key range queries or min/max queries are used for such databasesa better organization must be found one approach would be to use the binary search tree (bstto store primary and secondary key indices bsts can store duplicate key valuesthey provide efficient insertion and deletion as well as efficient searchand they can perform efficient range queries when there