An Analysis of Storage, Retrieval, and Update Costs for Data Bases which are Tables of Entries.

摘要

The performance of retrieval systems for tables of entries is investigated. The system costs considered are the cost of storing a representation of a table, the cost of retrieving an individual table entry, and the cost of updating the table by adding or deleting the last entry. Several systems are presented and their costs are analyzed. For each type of cost a lower bound is derived, though in some cases it is for a restricted situation (such as for bounded table size). It is found for the problem presented that the actual storage cost and the lower bound on storage cost are both on the order of lw+1g(l), where l is the number of entries in the table and w is the entry size. The bounds on both retrieval cost and update cost are found to be on the order of w, while the actual costs of the best systems presented are on the order of w+1g(l). (Author)