Stacked skip list data structures

Claim 2

A data structure stored in a digital computer memory comprising: a primary skip list of nodes, the primary skip list of nodes having a primary array of forward pointers, each node in the primary skip list using at least one forward pointer and having a node level field for recording a primary node level of such node, the primary node level corresponding to the number of extra forward pointers being used; and a secondary skip list of nodes, each node of the secondary skip list of nodes existing on the primary skip list of nodes, the secondary skip list of nodes having a secondary array of forward pointers, the secondary array of pointers including zero or more forward pointers of the primary pointer array which are unused by the node of the primary skip list of nodes, the primary node level providing an index into the primary array of forward pointers to locate the secondary array of forward pointers.

Claim 3

A data structure stored in a digital computer memory according to claim 1, wherein the primary skip list has a maximum level, further comprising: an additional secondary forward pointer in each node of the secondary skip list of nodes, the additional secondary forward pointer enabling insertion on the secondary skip list of any of the primary skip list nodes including a primary skip list node at the maximum level on the primary skip list.

Claim 4

A data structure stored in a digital computer memory according to claim 2, wherein the primary array of forward pointers includes a maximum level forward pointer corresponding to a maximum level of the primary skip list of nodes and the additional secondary forward pointer is adjacent to the maximum level forward pointer of the primary skip list of nodes.

Claim 5

A data structure stored in a digital computer memory according to claim 1 further comprising: a second node level field in each node within the nodes of the secondary skip list, the second node level field for storing a secondary node level associated with such node of the secondary skip list, the secondary node level indicating the number of forward pointers unused for the node of the primary skip list and being used by the node on the secondary skip list.

Claim 6

A data structure stored in a digital computer memory according to claim 1, wherein the nodes of the secondary skip list are a subset of the nodes of the primary skip list.

Claim 7

A data structure stored in a digital computer memory comprising: a primary skip list of nodes, the primary skip list of nodes having a primary array of forward pointers, each node in the primary list using at least one forward pointer and having a node level field for recording a primary node level of such node, the primary node level corresponding to the number of pointers being used; and a secondary skip list of nodes, the secondary skip list nodes being a subset of the nodes existing on the primary skip list, the secondary skip list of nodes each including a secondary array of forward pointers including zero or more of the forward pointers of the primary array of forward pointers unused by the node on primary skip list of nodes, the secondary skip list of nodes further including an additional secondary forward pointer in each node of the secondary skip list of nodes to ensure that a maximum level node on the primary skip list can be inserted on the secondary skip list.

Claim 8

A data structure stored in a digital computer memory comprising: a primary skip list of nodes, the primary skip list of nodes having a primary array of forward pointers, each node in the primary list using at least one forward pointer and having a node level field for recording a primary node level of such node, the primary node level corresponding to the number of pointers being used; and a secondary skip list of nodes, the secondary skip list nodes being a subset of the nodes existing on the primary skip list, the secondary skip list of nodes each including a secondary array of forward pointers including zero or more of the forward pointers of the primary array of forward pointers unused by the node on primary skip list of nodes, the secondary skip list of nodes further including an additional secondary forward pointer in each node of the secondary skip list of nodes to ensure that a maximum level node on the primary skip list can be inserted on the secondary skip list.

Claim 9

A digital computer system comprising: a memory; a data structure stored in the memory, the data structure including a primary skip list of nodes, the primary skip list of nodes having a primary array of forward pointers, each node in the primary skip list using at least one forward pointer and having a node level field for recording a primary node level of the node, the primary node level determined by the number of forward pointers being used, the data structure further including a secondary skip list of nodes, the secondary skip list nodes including zero or more of the nodes existing on the primary skip list and a secondary array of forward pointers, the secondary array of forward pointers including zero or more of the forward pointers of the primary array of forward pointers unused by the node on the primary skip list of nodes, the secondary skip list of nodes further including an additional secondary forward pointer in each node of the secondary skip list of nodes and a second node level field for storing a secondary node level associated with the corresponding node of the secondary skip list of nodes; and a system agent for performing maintenance operations on the primary and secondary skip lists, the system agent utilizing the node level field to index into the primary array of forward pointers to locate the secondary array of forward pointers.

Claim 10

A digital computer system comprising: a memory; a data structure stored in the memory, the data structure including a primary skip list of nodes, the primary skip list of nodes having a primary array of forward pointers, each node in the primary skip list using at least one forward pointer and having a node level field for recording a primary node level of the node, the primary node level determined by the number of forward pointers being used, the data structure further including a secondary skip list of nodes, the secondary skip list nodes including zero or more of the nodes existing on the primary skip list and a secondary array of forward pointers, the secondary array of forward pointers including zero or more of the forward pointers of the primary array of forward pointers unused by the node on the primary skip list of nodes, the secondary skip list of nodes further including an additional secondary forward pointer in each node of the secondary skip list of nodes and a second node level field for storing a secondary node level associated with the corresponding node of the secondary skip list of nodes; and a system agent for performing maintenance operations on the primary and secondary skip lists, the system agent utilizing the node level field to index into the primary array of forward pointers to locate the secondary array of forward pointers.

Claim 11

A digital computer system comprising: a memory; a data structure stored in the memory and describing cached data, the data structure including a normal skip list of nodes, the nodes of the normal skip list including flushable nodes describing dirty cached data, the normal skip list of nodes having a primary array of forward pointers, each node in the primary skip list using at least one forward pointer and having a node level field for recording a primary node level of the node, the primary node level determined by the number of forward pointers being used, the data structure further including a flush control skip list of nodes, the flush control skip list nodes including the flushable nodes occurring on the normal skip list and a secondary array of forward pointers, the secondary array of forward pointers including zero or more of the forward pointers of the primary array of forward pointers unused by the nodes of the normal skip list of nodes, the flush control skip list of nodes further including an additional secondary forward pointer in each node of the secondary skip list of nodes; and a system agent for performing a flush operation by locating the flushable nodes on the flush control skip list, the system agent utilizing the node level field to index into the primary array of forward pointers to locate the secondary array of forward pointers.

Claim 12

A digital computer system comprising: a memory; a data structure stored in the memory and describing cached data, the data structure including a normal skip list of nodes, the nodes of the normal skip list including flushable nodes describing dirty cached data, the normal skip list of nodes having a primary array of forward pointers, each node in the primary skip list using at least one forward pointer and having a node level field for recording a primary node level of the node, the primary node level determined by the number of forward pointers being used, the data structure further including a flush control skip list of nodes, the flush control skip list nodes including the flushable nodes occurring on the normal skip list and a secondary array of forward pointers, the secondary array of forward pointers including zero or more of the forward pointers of the primary array of forward pointers unused by the nodes of the normal skip list of nodes, the flush control skip list of nodes further including an additional secondary forward pointer in each node of the secondary skip list of nodes; and a system agent for performing a flush operation by locating the flushable nodes on the flush control skip list, the system agent utilizing the node level field to index into the primary array of forward pointers to locate the secondary array of forward pointers.