TELETRAFFIC THEORY APPLIED TO THE ANALYSIS OF HASH-STRUCTURED FILES

Certain hash-structured files consist of sequence,s (chains) of computer memory locations (slots) into which records are inserted, and from which they are later retrieved or deleted. If we assume that the records arrive to the file according to a Poisson process for insertion into a chain (randomly selected by the hash function), and reside in memory for a random length of time before being deleted, then we can associate this with a teletraffic model in which the records are ''calls'' and the slots in the chain are ''trunks.'' In particular, we consider two models: (1) hardpack, where a deleted record is immediately physically removed from the file and is replaced by the last record on its chain, and (2) softpack, where a deleted record is marked, and a subsequent arriving record is written over the first marked record on its chain. The slots can be accessed individually or in groups (called ''buckets''). In each case we are interested in the length of a successful search (the number of buckets inspected until an arbitrary record is located) and the length of an unsuccessful search (the number of buckets inspected until it is determined that an arbitrary record is not in the file). If we identify these file structures as analogous to trunk groups with ordered hunt, then these models can be analyzed using results obtained many years ago (in particular, Kosten (1937) and Burke (1971)) for teletraffic applications, results which are not well known or easily accessible to the database-performance-analysis community.