sec linear indexing linear index database records figure linear indexing for variable-length records each record in the index file is of fixed length and contains pointer to the beginning of the corresponding record in the database file begins with discussion of the variant normally referred to simply as " -tree section presents the most widely implemented variantthe -tree linear indexing linear index is an index file organized as sequence of key/pointer pairs where the keys are in sorted order and the pointers either ( point to the position of the complete record on disk( point to the position of the primary key in the primary indexor ( are actually the value of the primary key depending on its sizea linear index might be stored in main memory or on disk linear index provides number of advantages it provides convenient access to variable-length database recordsbecause each entry in the index file contains fixed-length key field and fixed-length pointer to the beginning of (variable-lengthrecord as shown in figure linear index also allows for efficient search and random access to database recordsbecause it is amenable to binary search if the database contains enough recordsthe linear index might be too large to store in main memory this makes binary search of the index more expensive because many disk accesses would typically be required by the search process one solution to this problem is to store second-level linear index in main memory that indicates which disk block in the index file stores desired key for examplethe linear index on disk might reside in series of -byte blocks if each key/pointer pair in the linear index requires bytesthen keys are stored per block the second-level indexstored in main memoryconsists of simple table storing the value of the key in the first position of each block in the linear index file this arrangement is shown in figure if the linear index requires disk blocks ( mb)the second-level index contains only entriesone per disk block to find which disk block contains desired search key valuefirst search through the