Cursor seek operations using deleted record spans

A method, comprising:

• receiving, by a processing device, a request to insert a first data element into a key-value data store, the request specifying a first key associated with the first data element and a first value specified with the first data element;
• determining that the first key is within a first range of deleted data elements comprising a first plurality of deleted data elements of the key-value data store;
• splitting the first range of deleted data elements into a second range of deleted data elements and a third range of deleted data elements, wherein the second range of deleted data elements comprises a first subset of the first range of deleted data elements and the third range of deleted data elements comprises a second subset of deleted data elements of the first range of deleted data elements;
• removing a deletion marker associated with the first key;
• and
• storing, in the key-value data store, the first value in association with the first key.

A system, comprising:

• a memory device to store a key-value data store;
• and
• a processing device, operatively coupled to the memory device, the processing device to perform operations comprising:
• receiving a request to search for a first data element of the key-value data store, the request specifying a first key associated with the first data element;
• determining that the first key is within a range of deleted data elements comprising a plurality of deleted data elements of the key-value data store;
• identifying a tail key associated with a tail element of the range of deleted data elements;
• identifying a second data element in the key-value data store, wherein the second data element is associated with a second key that follows the tail key in a specified order of keys;
• and
• providing the second data element in response to the request.