Access Restriction

Author Maruyama, K. ♦ Smith, S. E.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Key compression ♦ Pages ♦ Retrieval ♦ Search strategy ♦ Index structure ♦ Virtual memory ♦ Index ♦ Maintenance ♦ Files
Abstract 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 stuctured, and whether or not keys are compressed. The average cost of retrieving entries from these indexes is expressed as a weighted sum of the cost of a basis key comparison and the cost of crossing a page boundary in the index structure. Formulas for the retrieval costs 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 maintenance costs (insertion, deletion, reorganization) of the design alternatives are also included.
Description Affiliation: IBM Thomas J. Watson Research Center, Yorktown Heights, NY (Maruyama, K.; Smith, S. E.)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 20
Issue Number 4
Page Count 10
Starting Page 245
Ending Page 254

Open content in new tab

   Open content in new tab
Source: ACM Digital Library