Storing and searching a multikey table
Amos Fiat, Moni Naor, Alexandro Schäffer, Jeanette P. Schmidt, Alan R. Siegel · 1988
We describe an implicit data structure for n multikey records that supports searching for a record, under any key, in the asymptotically optimal search time Ο(log n). This improves on [Mun87] in which Munro describes an implicit data structure for the problem of storing n k-key records so that search on any key can be performed in Ο(logk n(log log n)k-1) comparisons. The theoretical tools we develop also yield practical schemes that either halve the number of memory references over obvious solutions to the non-implicit version of the problem, or alternatively reduce the number of pointers involved significantly.