Supporting random access in files of variable length records

Abstract

We consider the problem of providing a random access index to a static file of variable length records. For a file of N bits and O(N) records the index we describe occupies O(( N log log N) log N)=o(N) bits, and access to any record is possible after O(log N) bit accesses in the index and the file itself. © 1993.