Techniques are disclosed relating to maintaining a cache usable to locate data stored in a data structure. A computer system, in various embodiments, maintains a data structure having a plurality of levels that store files for a database. The files may include one or more records that each have a key and corresponding data. The computer system may also maintain a cache for the database whose entries store, for a key, an indication of a location of a corresponding record in a file of the data structure. In some embodiments, the computer system receives a request to access a particular record stored in the data structure where the request specifies a key usable to locate the particular record. The computer system may retrieve, from the cache via the key, a particular indication of a location of the particular record and may use the particular indication to access the particular record.