Performance Analyses of Cartesian Product Files and Random Files
Chia‐Chen Chang, Mingzhe Du, R. C. T. Lee · IEEE Transactions on Software Engineering · 1984
In this paper, we shall derive two formulas for the average number of buckets to be examined over all possible partial match queries for Cartesian product files and random files, respectively. The superiority of the Cartesian product file is established. A new multi-key file, called a partition file, is introduced. It is shown that both Cartesian product files and random files are special cases of partition files.