A system includes a memory device a processing device, operatively coupled to the memory device. The processing device is configured to receive a request to identify a target key in a key-value store based on a specified key; identify, in at least one of a plurality of sequences of memory keys, the target key based on the specified key, where the plurality of sequences of memory keys includes a sequence of memory keys and a sequence of media keys that comprises designated media keys, where each of the designated media keys is designated as being deleted, where the identifying comprises comparing each of the designated media keys to the specified key; and perform a database operation using the target key.