Cache for efficient record lookups in an lsm data structure

A non-transitory computer-readable medium having program instructions stored thereon that are capable of causing a computer system to perform operations comprising:

• maintaining a log-structured merge-tree (LSM tree) that includes a plurality of levels that store files of a database, wherein a first one of the files is included in a first level of the LSM tree and stores a record having data and a key;
• maintaining a cache whose entries store, for keys, indications of locations of corresponding records in the LSM tree, wherein a particular one of the entries stores, for the key, an indication of a location of the record of the first file in the first level of the LSM tree;
• performing a merge operation in which the record is copied into a second file of a second level of the LSM tree;
• receiving a request to access the record using the key;
• retrieving, from the cache using the key, the indication of the location of the record in the first file;
• and
• accessing, based on the indication, the record from the first file of the first level instead of the second file of the second level.

A system, comprising:

• at least one processor;
• and
• memory having program instructions stored thereon that are capable of causing a computer system to perform operations comprising:
• maintaining a log-structured merge-tree (LSM tree) that includes a plurality of levels that store files of a database, wherein a first one of the files is included in a first level of the LSM tree and stores a record having data and a key;
• maintaining a cache whose entries store, for keys, indications of locations of corresponding records in the LSM tree, wherein a particular one of the entries stores, for the key, an indication of a location of the record of the first file in the first level of the LSM tree;
• performing a merge operation in which the record is copied into a second file of a second level of the LSM tree;
• receiving a request to access the record using the key;
• retrieving, from the cache using the key, the indication of the location of the record in the first file;
• and
• accessing, based on the indication, the record from the first file of the first level instead of the second file of the second level.