TELETRAFFIC THEORY APPLIED TO THE ANALYSIS OF HASH-STRUCTURED FILES

Certain hash-structured files consist of sequence,s (chains) of comput er memory locations (slots) into which records are inserted, and from which they are later retrieved or deleted. If we assume that the recor ds arrive to the file according to a Poisson process for insertion int o a chain (randomly selected by the hash function), and reside in memo ry for a random length of time before being deleted, then we can assoc iate 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 physic ally removed from the file and is replaced by the last record on its c hain, and (2) softpack, where a deleted record is marked, and a subseq uent arriving record is written over the first marked record on its ch ain. The slots can be accessed individually or in groups (called ''buc kets''). In each case we are interested in the length of a successful search (the number of buckets inspected until an arbitrary record is l ocated) and the length of an unsuccessful search (the number of bucket s 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 resu lts obtained many years ago (in particular, Kosten (1937) and Burke (1 971)) for teletraffic applications, results which are not well known o r easily accessible to the database-performance-analysis community.