An optimization problem on the selection of secondary keys

Abstract

The use of index files for accessing records, on the basis of secondary key values is a common feature of existing information systems. This method, judiciously applied, provides major improvements in response time, is easy to implement and costs relatively little. Moreover, the concepts of secondary indexes are simple, yet powerful and flexible because they provide the power to handle all kinds of queries easily with little loss of efficiency. It is, however, important to carefully select the key fields to be indexed because excessive indexing can result in major performance degradation. This paper presents a quantitative tradeoff analysis for index selection.