This paper considers storage schemes for n k-key records as a simple n by k array with no pointer structuring the data, so that any structural information must be encoded in the ordering of the records. Queries are presented as j≤Ck key values and a record with those j key values is to be retrieved. A procedure developed previously by Munro [1] to order the n records for efficient retrieval is analyzed. It has been shown that this algorithm allows finding a record specified by j key values in O(n 1−j/k) comparisons if j < k and O (log - n) comparisons if j=k. The present paper proves that &OHgr; (n1−1/k) comparisons are necessary in the worst case to find a record specified by one key value (j=1) regardless of the ordering. The paper also conjectures that this lower bound holds even if j>1.
