System, method, and service for organizing data for fast retrieval
AssigneeInternational Business Machines Corporation
InventorsWindsor Sun Hsu, Shauchi Ong, Qingbo Zhu
Life of this patent
Estimating the term…
Abstract
A data organization system includes an index that offers fast retrieval of records and that protects records from logical modification. The index includes a balanced tree that grows from the root of the tree down to the leaves and requires no re-balancing. Each level in the tree includes a hash table. The hash table in each level in the tree can use a hash function that is different and independent from the hash function used in any other level in the tree. Alternatively, the hash table in each level in the tree can use a universal hash function. Possible locations of a record in the tree are fixed and determined by a hash function of a key of that record.
Claims20
A method of organizing data, comprising:
- obtaining a key for a record;
- performing a hash function on the key to generate a hash value indicative of a candidate position at which to insert the record in a tree;
- determining if the candidate position is available in the tree;
- performing at least one additional hash function on the key to generate at least one additional hash value indicative of at least one additional candidate position if the position is not available;
- determining if the at least one additional candidate position is available;
- creating a new node including a candidate position in the tree if the at least one additional candidate position is not available;
- and
- assigning the record to an available candidate position.
A computer program product including a plurality of executable instruction codes on a computer-readable medium, for organizing data, comprising:
- a first set of instruction codes for obtaining a key for a record;
- a second set of instruction codes for performing a hash function on the key to generate a hash value indicative of a candidate position at which to insert the record in a tree;
- a third set of instruction codes for determining if the candidate position is available in the tree;
- performing at least one additional hash function on the key to generate at least one additional hash value indicative of at least one additional candidate position if the position is not available;
- a fourth set of instruction codes for determining if the at least one additional candidate position is available;
- a fifth set of instruction codes for creating a new node including a candidate position in the tree if the at least one additional candidate position is not available;
- and
- a sixth set of instruction codes for assigning the record to an available candidate position.
A system for organizing data, comprising:
- an insertion module for obtaining a key for a record;
- the insertion module performing a hash function on the key to generate a hash value indicative of a candidate position at which to insert the record in a tree;
- the insertion module determining if the candidate position is available in the tree;
- performing at least one additional hash function on the key to generate at least one additional hash value indicative of at least one additional candidate position if the position is not available;
- the insertion module determining if the at least one additional candidate position is available;
- the insertion module creating a new node including a candidate position in the tree if the at least one additional candidate position is not available;
- and
- the insertion module assigning the record to an available candidate position.
Dependencies are inferred from the claim text.