Method and system for efficiently retrieving information from a database
First Claim
1. A method of cataloging information in a database, comprising:
- determining a key for referencing a record of information stored in a database;
determining a record address for the record in the database;
determining a first cyclical redundancy check value for the key; and
storing a tuple in an index at a position corresponding to at least a portion of the first cyclical redundancy check value, said tuple containing the record address and at least a portion of a second cyclical redundancy check value determined for the key.
1 Assignment
0 Petitions
Accused Products
Abstract
A method for fast and efficient record retrieval in large databases using cyclical redundancy check (CRC) computations as hash functions. Two hash values are computed for each record'"'"'s key using the CRC-CCITT and CRC-16 generator polynomials. The two CRC values then are combined into a four-byte composite hash value that represents a binary signature of the record'"'"'s key. Alternately, a single CRC-32 value can be used as a four-byte hash value. In most cases, this four-byte hash value uniquely identifies the record'"'"'s key. An index file is constructed using a hybrid search method, part hash table and part linear search. The index file is searched to find a match for the four-byte hash value and the record'"'"'s offset is obtained. The record'"'"'s offset is used to retrieve the record from the database.
-
Citations
21 Claims
-
1. A method of cataloging information in a database, comprising:
-
determining a key for referencing a record of information stored in a database;
determining a record address for the record in the database;
determining a first cyclical redundancy check value for the key; and
storing a tuple in an index at a position corresponding to at least a portion of the first cyclical redundancy check value, said tuple containing the record address and at least a portion of a second cyclical redundancy check value determined for the key. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16)
-
-
17. A method of obtaining a record of information from a database, comprising:
-
determining a key for referencing the record in the database;
determining a cyclical redundancy check value for the key;
determining a position in an index corresponding to at least a portion of the calculated cyclical redundancy check value;
determining a second cyclical redundancy check value for the key; and
retrieving from a memory pointed to by contents of said index at said position one or more tuples, where each tuple contains an address field A and a value field, and selecting the address field of a retrieved tuple whose value field is equal to at least a portion of said second cyclical redundancy check value. - View Dependent Claims (18, 19, 20, 21)
-
Specification