STORING ENTRIES AS ORDERED LINKED LISTS

• US 20160253433A1
• Filed: 02/26/2015
• Published: 09/01/2016
• Est. Priority Date: 02/26/2015
• Status: Active Grant

• Current Assignee: Red Hat, Inc. (International Business Machines Corporation)
• Original Assignee: Red Hat, Inc. (International Business Machines Corporation)
• Inventors: Mozaffari, Babak
• Granted Patent: US 11,449,549 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence

Abstract

A processor stores a first data item in a first entry of a data structure in association with a first key. The processor stores a second data item in a second entry of the data structure in association with the second key. The processor causes the second entry of the data structure to reference the first entry of the data structure. The processor stores the second key in a third entry of the data structure in association with a business key. The business key is employed to identify a plurality of entries of the data structure comprising the first entry and the second entry.

Claims

1. A method comprising:

storing a first data item in a first entry of a data structure in association with a first key;

storing a second data item in a second entry of the data structure in association with a second key;

causing the second entry of the data structure to reference the first entry of the data structure; and

storing the second key in a third entry of the data structure in association with a business key, wherein the business key is employed to identify a plurality of entries of the data structure comprising the first entry and the second entry.

2. The method of claim 1, further comprising:

storing a third data item in a fourth entry of the data structure in association with a third key;

causing the fourth entry of the data structure to reference the second entry of the data structure; and

updating the third entry of the data structure to store the third key in association with the business key.

3. The method of claim 1, further comprising:

removing the first entry from the data structure; and

removing, from the second entry, a reference to the first entry.

4. The method of claim 1, wherein storing the first entry comprises randomly generating the first key.

5. The method of claim 1, wherein storing the second entry comprises randomly generating the second key.

6. The method of claim 1, further comprising:

receiving a request for data entries associated with a specified business key value; and

identifying one or more data entries associated with a chain of data entries associated with the specified business key value.

7. The method of claim 1, wherein the second data item is a least recently updated data item.

8. The method of claim 1, wherein the data structure is provided by a hash table.

9. A system comprising:

a memory; and

a processor operatively coupled to the memory, the processor to;

store a first data item in a first entry of a data structure in association with a first key;

store a second data item in a second entry of the data structure in association with a second key;

cause the second entry of the data structure to reference the first entry of the data structure; and

store the second key in a third entry of the data structure in association with a business key, wherein the business key is employed to identify a plurality of entries of the data structure comprising the first entry and the second entry.

10. The system of claim 9, the processor further to:

store a third data item in a fourth entry of the data structure in association with a third key;

cause the fourth entry of the data structure to reference the second entry of the data structure; and

update the third entry of the data structure to store the third key in association with the business key.

11. The system of claim 9, the processor further to:

remove the first entry from the data structure; and

remove, from the second entry, a reference to the first entry.

12. The system of claim 9, wherein storing the first entry comprises randomly generating the first key.

13. The system of claim 9, the processor further to:

receive a request for data entries associated with a specified business key value; and

identify one or more data entries associated with a chain of data entries associated with the specified business key value.

14. A non-transitory computer readable storage medium that comprises instructions that, when executed by a processor, cause the processor to:

store a first data item in a first entry of a data structure in association with a first key;

store a second data item in a second entry of the data structure in association with a second key;

cause the second entry of the data structure to reference the first entry of the data structure; and

store the second key in a third entry of the data structure in association with a business key, wherein the business key is employed to identify a plurality of entries of the data structure comprising the first entry and the second entry.

15. The non-transitory computer readable storage medium of claim 14, the instructions to cause the processor further to:

store a third data item in a fourth entry of the data structure in association with a third key;

cause the fourth entry of the data structure to reference the second entry of the data structure; and

update the third entry of the data structure to store the third key in association with the business key.

16. The non-transitory computer readable storage medium of claim 14, wherein storing the first entry comprises randomly generating the first key.

17. The non-transitory computer readable storage medium of claim 14, wherein storing the second entry comprises randomly generating the second key.

18. The non-transitory computer readable storage medium of claim 14, the instructions to cause the processor further to:

remove the first entry from the data structure; and

remove, from the second entry, a reference to the first entry.

19. The non-transitory computer readable storage medium of claim 14, the instructions to cause the processor further to:

receive a request for data entries associated with a specified business key value; and

identify one or more data entries associated with a chain of data entries associated with the specified business key value.

20. The non-transitory computer readable storage medium of claim 14, wherein the second data item is a least recently updated data item.