Skip list with address related table structure

Details Skip list with address related table structure Skip list with address related table structure

2005-06-24

2010-11-09

Rones, Charles (Department: 2164)

Data processing: database and file management or data structures

Database design

Data structure types

Reexamination Certificate

active

07831624

ABSTRACT:
Apparatus and method for efficiently arranging and searching data in a memory space, such as a cache memory of a data storage array controller. A data structure comprises a skip list of nodes having an array of forward pointers. Each node has a node level derived from an index at which the node is stored in a table in the memory space. The total available number of nodes is preferably selected to be less than half of the largest power of 2 that can be expressed by a number of bits of the index, and the nodes are preferably stored at only even or only odd indices of the table. In such case, a free list of nodes is preferably generated from an array of pairs of counts and indices to identify the available nodes. Additional table structures can further be provided to enhance data arrangement and searching functions.

REFERENCES:
patent: 5761501 (1998-06-01), Lubbers et al.
patent: 6088701 (2000-07-01), Whaley et al.
patent: 6117185 (2000-09-01), Schmidt
patent: 6216199 (2001-04-01), DeKoning et al.
patent: 6243783 (2001-06-01), Smyers et al.
patent: 6246682 (2001-06-01), Roy et al.
patent: 6567896 (2003-05-01), James
patent: 6654760 (2003-11-01), Baskins et al.
patent: 6671694 (2003-12-01), Baskins et al.
patent: 2002/0087500 (2002-07-01), Berkowitz et al.
patent: 2004/0054807 (2004-03-01), Harvey et al.
patent: 2004/0107346 (2004-06-01), Goodrich et al.
William Pugh, “Skip Lists: A Probabilistic Alernative To Balanced Trees,” Communications of the ACM, 33 ed., No. 6, p. 668-676, (Jun. 23, 1990).

Affiliated with

Also associated with

Rating

Skip list with address related table structure does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Skip list with address related table structure, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Skip list with address related table structure will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4172691