Analysis of Design Alternatives for Virtual Memory Indexes A class of index structures for use in a virtual memory environment is described. Design alternatives within this class of index structures are analyzed. These alternatives include a choice of search strategy, whether or not pages in the index are structured, and whether or not keys are compressed. The average cost of retrieving entries from these indexes is expressed as a wieghted sum of the cost of a basic key comparison and the cost of crossing a page boundary in the index structure. Formulas for the retrieval costs for possible combinations of design alternatives are given. These are used in numerical case studies which compare the retrieval costs of the alternatives. Qualitative comparisons of the main tenance costs (insertion, deletion, reorganization) of the design alternatives are also included. CACM April, 1977 Maruyama, K. Smith, S. E. index, index structure, pages, virtual memory, files, retrieval, main tenance, search strategy, key compression 3.50 3.51 3.02 3.73 3.74 CA770404 JB December 29, 1977 5:22 AM 2451 4 2978 2556 4 2978 2978 4 2978 1935 5 2978 2978 5 2978 2978 5 2978 2978 5 2978 3058 5 2978 3063 5 2978 2978 6 2978 2978 6 2978