Method and system for efficiently retrieving information from a database

• US 6,865,577 B1
• Filed: 11/06/2000
• Issued: 03/08/2005
• Est. Priority Date: 11/06/2000
• Status: Expired due to Term

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Sereda, Gregory
• Primary Examiner(s): ROBINSON, GRETA LEE
• Application Number:
  US09/707,462
• Time in Patent Office: 1,583 Days
• Field of Search: 707/1, 707/2, 707/100, 707/3
• US Class Current: 707/699
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: Y10S 707/99931 Database or file accessing

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.

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.

2. The method of cataloging information recited in claim 1, wherein the first cyclical redundancy check value is a CRC-CCITT, CRC-16, or CRC-32 cyclical redundancy check value.

3. The method of cataloging information recited in claim 2, wherein the cyclical redundancy check value is a CRC-16 cyclical redundancy check value.

4. The method of cataloging information recited in claim 1, wherein the at least a portion of the first cyclical redundancy check value encompasses values defined by a first preselected set of bits of said first cyclical redundancy check value.

5. The method of cataloging information recited in claim 1, wherein the at least a portion of the second cyclical redundancy check value encompasses values defined by a second preselected set of bits of said second cyclical redundancy check value.

6. The method of cataloging information recited in claim 5, wherein the at least a portion of the second cyclical redundancy check value is the same as the at least a portion of the first cyclical redundancy check value.

7. The method of cataloging information recited in claim 5, wherein the first cyclical redundancy check value is also the second cyclical redundancy check value, and said first set of preselected bits is different from said second set of preselected bits.

8. The method of cataloging information recited in claim 5, wherein the first cyclical redundancy check value is also the second cyclical redundancy check value, and said first set of preselected bits is disjoint from said second set of preselected bits.

9. The method of cataloging information recited in claim 5, wherein the first cyclical redundancy check value is also the second cyclical redundancy check value, and bits in said second set of preselected bits are at least some of the bits not included in said first set of preselected bits.

10. The method of cataloging information recited in claim 1 further comprising the step of storing the record in one of a plurality of physically separate storage devices based on at least a portion of the second cyclical redundancy check value.

11. The method of cataloging information recited in claim 1, further including

determining a third cyclical redundancy check value for the key;

and

storing the record on one of a plurality of storage devices based upon at least a portion of the third cyclical redundancy check value.

12. The method of cataloging information recited in claim 11, wherein the third cyclical redundancy check value is the same as the first cyclical redundancy check value.

13. The method of cataloging information recited in claim 11, wherein the at least a portion of the third cyclical redundancy check value is the same as the second cyclical redundancy check value or a portion thereof.

14. The method of cataloging information recited in claim 1, wherein the index is divided into index table clusters, each index table cluster having K number of entries with each entry having L number of locations;

and

further including

sequentially checking a status of each entry in an index table cluster corresponding to the at least a portion of the cyclical redundancy check value until a first unused entry available to store the record address is recognized, and

storing the record address in the recognized first available unused entry.

15. The method of cataloging information recited in claim 14, further including

if an unused entry available to store the record address is not recognized from sequentially checking a status of each entry in the index table cluster corresponding to the at least a portion of the cyclical redundancy check value, then

creating a second index table cluster corresponding to the at least a portion of the cyclical redundancy check value in the index;

storing an address of the second index table cluster in the first index table cluster; and

storing the record address in a first available unused entry of the second index table cluster.

16. The method of cataloging information recited in claim 14, wherein an initial location of the index table cluster corresponding to the at least a portion of the cyclical redundancy check value is positioned at an offset Index(N)=N*K*L, where N is the at least a portion of the cyclical redundancy check value.

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.

18. The method of obtaining a record of information from a database recited in claim 17, wherein the first cyclical redundancy check value is a CRC-CCITT. CRC-16. or CRC-32 cyclical redundancy check value.

19. The method of obtaining a record of information from a database recited in claim 17, wherein the memory pointed to by contents of said index at said position is an index cluster, and said retrieving tuples proceeds until a tuple is found where the value field of the retrieved tuple equals said at least a portion of said second cyclical redundancy check value.

20. The method of obtaining a record of information from a database recited in claim 17, wherein

the memory pointed to by contents of said index at said position is an index cluster, and

said retrieving tuples

proceeds until all tuples in said index cluster have been retrieved;

when a single tuple is found where the value field of the retrieved tuple equals said at least a portion of said second cyclical redundancy check value retrieving said record based on the address field of said single tuple

when a number of tuples are found where the value field of the retrieved tuple equals said at least a portion of said second cyclical redundancy check value,

retrieving a record associated with each retrieved tuple where the value field is equal to said at least a portion of said second cyclical redundancy check value and

comparing key of each retrieved record to said key.

21. The method of obtaining a record of information from a database recited in claim 17, wherein

the index is divided into index table clusters, each index table cluster having K number of index entries with each index entry having L number of locations;

and

an initial location of an index table cluster corresponding to the at least a portion of the cyclical redundancy check value is positioned at an offset Index(N)=N*K*L, where N is the at least a portion of the cyclical redundancy check value.