An analytical comparison of two secondary index schemes: Physical versus logical addresses

摘要

The use of indexes usually improves the performance of queries but degrades the performance of updates, inserts and deletes. This paper focuses on reducing the cost of index maintenance when tuples are inserted or deleted. We present a scheme where secondary indexes contain logical as opposed to physical pointers. We develop an analytical model for the total cost of processing queries, updates, inserts and deletes, for this scheme and compare it with the cost of the typical secondary index scheme that uses physical pointers. We find by modifying the parameters that reduce the query cost, such as reducing the probability of occurrence of a query or reducing the average selectivity of a secondary key that the logical pointer scheme can achieve a better performance than the physical pointer scheme. However, selecting one scheme over the other is highly dependent on a number of parameters that are germane to the particular database application environment.