Cursor seek operations using deleted record spans
An example method of cursor seek operations using deleted record spans in memory sub-systems comprises: receiving, by a processing device, a request to search for a first data element of a 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.
1. A method comprising:
receiving, by a processing device, a request for a data element identified by any key that is lexicographically greater than or equal to a first key specified by the request;
determining that the first key is within a range of deleted data elements of a key-value data store;
identifying a tail key associated with a tail element of the range of deleted data elements;
performing a cursor seek operation by identifying, in the key-value data store, the data element identified by a second key that immediately follows the tail key in a specified order of keys; and
providing the data element in response to the request.
2. The method of claim 1 , wherein at least one deleted data element of the range of deleted data elements comprises a pointer referencing a head element of the range of deleted data elements.
3. The method of claim 1 , wherein at least one deleted data element of the range of deleted data elements comprises a pointer referencing the tail element of the range of deleted data elements.
4. The method of claim 1 , wherein keys of a plurality of data elements of the range of deleted data elements are lexicographically ordered.
5. The method of claim 1 , wherein identifying the tail key associated with the tail element of the range of deleted data elements further comprises:
identifying a head element of the range of deleted data elements, wherein the head element is referenced by the first key; and
identifying the tail element of the range of deleted data elements, wherein the tail element is referenced by a second pointer of the head element.
6. The method of claim 5 , wherein a head flag of the head element is set to a first value.
7. The method of claim 1 , further comprising:
receiving a request to delete the data element;
modifying a first pointer of a head element of the range of deleted data elements to reference the data element;
setting a second pointer of the data element to reference the head element of the range of deleted data elements; and
associating a deletion marker with the data element.
8. A computer-readable non-transitory storage medium comprising executable instructions that, when executed by a processing device, cause the processing device to:
receiving, by a processing device, a request for a data element identified by any key that is lexicographically greater than or equal to a first key specified by the request;
determining that the first key is within a range of deleted data elements of a key-value data store;
performing a cursor seek operation by identifying a tail key associated with a tail element of the range of deleted data elements;
identifying, in the key-value data store, the data element identified by a second key that immediately follows the tail key in a specified order of keys; and
providing the data element in response to the request.
9. The computer-readable non-transitory storage medium of claim 8 , wherein at least one deleted data element of the range of deleted data elements comprises a pointer referencing a head element of the range of deleted data elements.
10. The computer-readable non-transitory storage medium of claim 8 , wherein at least one deleted data element of the range of deleted data elements comprises a pointer referencing the tail element of the range of deleted data elements.
11. The computer-readable non-transitory storage medium of claim 8 , wherein keys of a plurality of data elements of the range of deleted data elements are lexicographically ordered.
12. The computer-readable non-transitory storage medium of claim 8 , wherein identifying the tail key associated with the tail element of the range of deleted data elements further comprises:
identifying a head element of the range of deleted data elements, wherein the head element is referenced by the first key; and
identifying the tail element of the range of deleted data elements, wherein the tail element is referenced by a second pointer of the head element.
13. The computer-readable non-transitory storage medium of claim 12 , wherein a head flag of the head element is set to a first value.
14. 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 for a data element identified by any key that is lexicographically greater than or equal to a first key specified by the request;
determining that the first key is within a range of deleted data elements of a key-value data store;
identifying a tail key associated with a tail element of the range of deleted data elements;
performing a cursor seek operation by identifying, in the key-value data store, the data element identified by a second key that immediately follows the tail key in a specified order of keys; and
providing the data element in response to the request.
15. The system of claim 14 , wherein at least one deleted data element of the range of deleted data elements comprises a pointer referencing a head element of the range of deleted data elements.
16. The system of claim 14 , wherein at least one deleted data element of the range of deleted data elements comprises a pointer referencing the tail element of the range of deleted data elements.
17. The system of claim 14 , wherein keys of a plurality of data elements of the range of deleted data elements are lexicographically ordered.
18. The system of claim 14 , wherein identifying the tail key associated with the tail element of the range of deleted data elements further comprises:
identifying a head element of the range of deleted data elements, wherein the head element is referenced by a first pointer of the first data element; and
identifying the tail element of the range of deleted data elements, wherein the tail element is referenced by a second pointer of the head element.
19. The system of claim 18 , wherein a head flag of the head element is set to a first value.
20. The system of claim 14 , wherein the operations further comprise:
receiving a request to delete the data element;
modifying a first pointer of a head element of the range of deleted data elements to reference the data element;
associating a second pointer of the data element to reference the head element of the range of deleted data elements; and
associating a deletion marker with the data element.