Key-value storage using a skip list

Patent metadata

Field	Value
Publication number	US-11544271-B2
Application number	US-202016908097-A
Country	US
Kind code	B2
Filing date	Jun 22, 2020
Priority date	Jan 31, 2017
Publication date	Jan 3, 2023
Grant date	Jan 3, 2023

Abstract

This disclosure provides various techniques that may allow for accessing values stored in a data structure that stores multiple values corresponding to database transactions using a skip list. A key may be used to traverse the skip list to access data associated with the key. The skip list maintains on ordering of multiple keys, each associated with a particular record in the data structure, using indirect links between data records in the data structure that reference buckets included in hash table. Each bucket includes pointers to one or more records in the skip list.

First claim

What is claimed is:

1. 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 plurality of hash buckets that store pointers to database records;
maintaining a buffer that stores a set of database records associated with a set of database keys, wherein the set of database records implement a skip list that allows for ones of the set of database records to be accessed in key-sorted order, and wherein a first database record indirectly points to a second database record by storing, as part of the skip list, a pointer to a particular one of the plurality of hash buckets that in turn stores a pointer to the second database record;
performing an insertion procedure to insert a third database record into the buffer, wherein the insertion procedure includes:
identifying a predecessor database record that is associated with a database key that precedes, in key-sorted order, a database key associated with the third database record; and
updating the skip list by modifying the predecessor database record to indirectly point to the third database record; and

performing a removal procedure to remove the second database record from the buffer, wherein the removal procedure includes:
updating the skip list by modifying the first database record to indirectly point to a fourth database record instead of the second database record; and
removing the second database record from the buffer.

2. The medium of claim 1 , wherein the insertion procedure further includes:
identifying a successor database record that is associated with a database key that succeeds, in key-sorted order, the database key associated with the third database record; and
updating the skip list by modifying the successor database record to indirectly point to the third database record.

3. The medium of claim 1 , wherein the plurality of hash buckets are associated with a corresponding plurality of hash bucket identifiers.

4. The medium of claim 3 , wherein the operations further comprise:
hashing a database key to determine, from the plurality of hash buckets, a hash bucket that includes a pointer to a particular one of the set of database records that implements a portion of the skip list; and
accessing, via the particular database record using the pointer included in the hash bucket, the skip list to traverse ones of the set of database records in key-sorted order.

5. The medium of claim 3 , wherein the operations further comprise:
populating an array with bucket identifiers from ones of the plurality of hash buckets whose associated database keys precede the database key of the third database record.

6. The medium of claim 5 , wherein the insertion procedure further includes:
sorting the array according to bucket identifier; and
latching ones of the plurality of hash buckets according to an order defined by the array as part of inserting the third database record into the buffer.

7. The medium of claim 1 , wherein the operations further comprise:
prior to removing the second database record, relocating the second database record within in the buffer as part of a defragmentation process.

8. A method, comprising:
maintaining, by a computer system, a plurality of hash buckets that store pointers to database records;
maintaining, by the computer system, a buffer that stores a set of database records associated with a set of database keys, wherein the set of database records implement a skip list that allows for ones of the set of database records to be accessed in key-sorted order, and wherein a first database record indirectly points to a second database record by storing, as part of the skip list, a pointer to a particular one of the plurality of hash buckets that in turn stores a pointer to the second database record; and
performing, by the computer system, a removal procedure to remove the second database record from the buffer, wherein the removal procedure includes:
updating the skip list by modifying the first database record to indirectly point to a third database record instead of the second database record; and
removing the second database record from the buffer.

9. The method of claim 8 , further comprising:
performing, by the computer system, an insertion procedure to insert a third database record into the buffer, wherein the insertion procedure includes:
identifying a predecessor database record that is associated with a database key that precedes, in key-sorted order, a database key associated with the third database record; and
updating the skip list by modifying the predecessor database record to indirectly point to the third database record.

10. The method of claim 8 , further comprising:
prior to removing the second database record from the buffer, in response to a change in location of the second database record in the buffer, the computer system updating the particular hash bucket to indicate the changed location of the second database record.

11. The method of claim 8 , further comprising:
prior to removing the second database record, the computer system accessing the second database record, wherein the accessing includes:
hashing a database key associated with the second database record to access the particular hash bucket that stores the pointer to the second database record; and
accessing the second database record using the pointer stored in the particular hash bucket.

12. The method of claim 8 , wherein the skip list comprises a plurality of levels of pointers that link ones of the set of database records, and wherein at least two database records indirectly point to the second database record.

13. The method of claim 12 , wherein updating the skip list includes modifying the at least two database records to indirectly point to one or more other database records than the second database record, and wherein the at least two database records include the first database record.

14. A method, comprising:
maintaining, by a computer system, a plurality of hash buckets that store pointers to database records;
maintaining, by the computer system, a buffer that stores a set of database records associated with a set of database keys, wherein the set of database records implement a skip list that allows for ones of the set of database records to be accessed in key-sorted order, and wherein a first database record indirectly points to a second database record by storing, as part of the skip list, a pointer to a particular one of the plurality of hash buckets that in turn stores a pointer to the second database record; and
performing, by the computer system, a procedure to insert a third database record into the buffer, wherein the procedure includes:
identifying a predecessor database record that is associated with a database key that precedes, in key-sorted order, a database key associated with the third database record; and
updating the skip list by modifying the predecessor database record to indirectly point to the third database record.

15. The method of claim 14 , wherein the procedure includes:
identifying a successor database record that is associated with a database key that succeeds, in key-sorted order, a database key associated with the third database record; and
updating the skip list by modifying the successor database record to indirectly point to the third database record.

16. The method of claim 14 , further comprising:
in response to a change in location of the second database record in the buffer, the computer system:
updating the pointe

Assignees

• Salesforce Com Inc

Inventors

• Helland Patrick James
• Mace James E
• Fanghaenel Thomas

Classifications

• G06F16/24562 Primary

  Pointer or reference processing operations · CPC title