On the selection of secondary indexes

Abstract

The selection of secondary indexes to use for speeding up the access to information is one of the key problems in data organization. While in general, the provision of indexes facilitate data retrieval, we are also expected to pay a certain amount of various costs. Therefore, the gains and costs to index an attribute or field must be analyzed on individual basis. Lumi and King2 in their papers, analyzed the problem of single attribute indexes with maintenance. Stonebraker3 analyzed a similar problem allowing the indexes to be combined, but taking into consideration only retrieval time. Here we would like to follow the approach of Lum and King but propose a much simpler version which can be used as a rule of thumb for index selection.