Adaptive probabilistic indexing with skip lists

Patent metadata

Field	Value
Publication number	US-9824105-B2
Application number	US-201213460072-A
Country	US
Kind code	B2
Filing date	Apr 30, 2012
Priority date	Apr 30, 2012
Publication date	Nov 21, 2017
Grant date	Nov 21, 2017

Abstract

A method of indexing in a skip list is disclosed. Key/value pairs are randomly inserted at an appropriate page in a skip list. A new page is created at the lowest level in the skip list. When creating the new page, the page is incremented to a higher level with a write probability. Reading the new page during a search. When reading the new page, the page is incremented to a higher level with a read probability. The read probability is not equal to the write probability.

First claim

What is claimed is:

1. A method, comprising:
receiving information regarding read and write operations on a virtual memory configured to store data, wherein the virtual memory is allocated in a plurality of pages;
inserting a node in a skip list having a plurality of levels, wherein the node corresponds with a page of the plurality of pages in the virtual memory ;
creating a new node at a lowest level in the skip list during a write operation to a new page not represented in the skip list, wherein the new node corresponds with the new page, and wherein creating the new node includes incrementing the new node to a higher level of the skip list as determined by comparing a selected value with a preselected write probability; and
reading from the new page during a read operation, wherein reading from the new page includes incrementing the corresponding node to a higher level of the skip list as determined by comparing a selected value with a preselected read probability, wherein the read probability is not equal to the write probability.

2. The method of claim 1 wherein the read probability and the write probability are selected based on distributions of read requests and write requests.

3. The method of claim 1 wherein one of the read probability and the write probability are selected from a set of values within the set of [0.2 . . . 0.5].

4. The method of claim 3 wherein the other of the read probability and the write probability equals zero.

5. The method of claim 1 wherein the write probability equals zero.

6. The method of claim 5 wherein no pointers at levels greater than the lowest level are updated from creating the new node.

7. The method of claim 6 wherein pointers of the new node and a previous node at the lowest level are updated from creating the new node.

8. The method of claim 5 wherein no pointers at the lowest level are updated from reading the page corresponding with the new node.

9. The method of claim 8 wherein pointers of the new node and a previous node are updated at a level greater than the lowest level when reading the page corresponding with the new node.

10. The method of claim 9 wherein pointer of the new node and a previous node are updated at levels greater than the lowest level when reading the page corresponding with the new node.

11. The method of claim 1 wherein the new node and a previous node pointing to the new node at the lowest level are locked to update pointers at the lowest level at write time, and wherein the new node and the previous node are locked to update pointers at higher levels than the lowest level at read time.

12. A computer readable storage medium storing instructions for controlling a processor to perform a method comprising:
receiving information regarding read and write operations on a virtual memory configured to store data, wherein the virtual memory is allocated in a plurality of pages;
inserting a node in a skip list having a plurality of levels, wherein the node corresponds with a page of the plurality of pages in the virtual memory;
creating a new node at a lowest level in the skip list during a write operation to a new page not represented in the skip list, wherein the new node corresponds with the new page, and wherein creating the new node includes incrementing the new node to a higher level of the skip list as determined by comparing a selected value with a preselected write probability; and
reading the from new page during a read operation, wherein reading from the new page includes incrementing the corresponding node to a higher level of the skip list as determined by comparing a selected value with a preselected read probability, wherein the read probability is not equal to the write probability.

13. The computer readable medium of claim 12 wherein the skip list has a lowest level and a maximum level, and wherein incrementing the node to a higher level includes not incrementing the node after reaching the maximum level.

14. The computer readable medium of claim 12 wherein the new node and a previous node pointing to the new node at the lowest level are locked to update pointers at the lowest level at write time, and wherein the new node and the previous node are locked to update pointers at higher levels than the lowest level if the node is updated at read time.

15. The computer readable medium of claim 12 wherein the skip list is created as a data structure in a storage medium.

16. The computer readable medium of claim 12 wherein one of the read probability and the write probability is zero.

17. The computer readable medium of claim 16 wherein the read probability is zero and reading the node does not increment the node to a higher level.

18. A method, comprising:
receiving information regarding read and write operations on a virtual memory configured to store data, wherein the virtual memory is allocated in a plurality of pages;
populating a storage medium with a skip list having a plurality of nodes at each of a plurality of levels, wherein each node in a given level has a probability p of extending into the next highest level, wherein p is greater than zero and less than one, and wherein the each node of the plurality of nodes corresponds with a page in the virtual memory;
creating a new node at a lowest level in the skip list during a write operation to a page not represented in the skip list; wherein creating the new node includes incrementing the new node to a higher level of the skip list as determined by comparing a selected value with a preselected write probability; and
reading from the new page during a read operation, wherein reading from the new page includes incrementing the corresponding node to a higher level of the skip list as determined by comparing a selected value with a preselected read probability, wherein the read probability is not equal to the write probability.

19. The method of claim 18 wherein the write probability is equal to zero.

20. The method of claim 18 wherein the probability p is selected from the set [0.2 . . . 0.5].

Assignees

• Kosuru Ramakumar
• Hewlett Packard Entpr Dev Lp

Inventors

• Kosuru Ramakumar

Classifications

• G06F16/2246 Primary

  Trees, e.g. B+trees · CPC title

• G06F17/30327 Primary

  Physics · mapped topic