Method and data structure for a low memory overhead database

• US 7,058,642 B2
• Filed: 03/20/2002
• Issued: 06/06/2006
• Est. Priority Date: 03/20/2002
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Kurupati, Sreenath, Guerrero, Miguel A.
• Primary Examiner(s): Pardo, Thuy N.
• Application Number:
  US10/102,968
• Publication Number:
  US 20030182291A1
• Time in Patent Office: 1,539 Days
• Field of Search: 707/101, 707/102, 707/103, 707/104, 707/2, 707/100, 707/3, 707/4, 707/200, 711/216, 370/389
• US Class Current: 1/1
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: G06F 16/289 Object oriented databases
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

Method and data structure for a low memory overhead database and apparatus for implementing the same. Under one embodiment, the data structure includes an index table for storing a plurality of entries, each of the entries corresponding to one of a plurality of hash values, with each entry including a section pointer to identify a memory address of one of a plurality of sections of a key database and including valid bits to indicate a size of the respective section of the key database. The key database is stores a plurality of data entries, with each data entry including a search key having one of the plurality of hash values, and wherein the data entries are grouped into the plurality of sections, with each section storing data entries with search keys having the same hash value.

Claims

1. A device comprising:

a key generation unit, the key generation unit to access data in a received packet and generate a key containing at least a portion of the data;

a hashing unit, the hashing unit to receive a key from the key generation unit and apply a hashing function to the received key to create an n-bit hash value;

a first memory to store a key database, the key database including a number of sizes of sections, each of the sections to store at least one data entry, wherein each of the data entries within a section includes a key having the same hash value;

a number of head pointer registers, the number of head pointer registers equal to the number of sizes, each of the number of head pointer registers to identify a first free section of one of the sizes of sections; and

a second memory coupled with the first memory and the hashing unit, the second memory to store an index table, the index table including a number of entries, each of the entries corresponding to one n-bit hash value, said each entry including a number of valid bits to indicate allocation of one of the sections of the key database and a section pointer to identify a location in the first memory of the allocated section.

2. The device of claim 1, wherein the number of valid bits in said each entry of the index table equals the number of sizes of sections in the key database.

3. The device of claim 2, a number of the valid bits set high to indicate a size of the allocated section.

4. The device of claim 1, wherein the number of valid bits in said each entry of the index table equals one.

5. The device of claim 1, wherein the number of entries in the index table is equal to 2ⁿ.

6. The device of claim 1, wherein the at least one data entry includes a key and a rule.

7. The device of claim 6, wherein the at least one data entry further includes a timestamp.

8. The device of claim 1, the first memory and the second memory comprising a single integrated memory.

9. The device of claim 8, wherein the single integrated memory comprises a random access memory.

10. The device of claim 8, wherein the single integrated memory comprises an external memory.

11. The device of claim 8, wherein the key generation unit, the hashing unit, the single integrated memory, and the head pointer registers form at least part of a single integrated circuit device.

12. The device of claim 1, each of the first memory and the second memory comprising random access memory.

13. The device of claim 1, wherein at least one of the first memory and the second memory comprises an external memory.

14. The device of claim 1, wherein the key generation unit, the hashing unit, the first memory, the head pointer registers, and the second memory form at least part of a single integrated circuit device.

15. A method comprising:

storing a number of data entries in a first section of a key database, the first section allocated to one of a plurality of entries of an index table responsive to a hash function applied to a key, a size of the first section corresponding to the number of data entries, each of the data entries of the first section including a key having a same hash value;

receiving a data entry including a key;

generating the hash value by applying a hash function to the received key;

allocating a second section of the key database to the one entry of the index table responsive to the hash value, a size of the second section greater than the size of the first section.

16. The method of claim 15, further comprising inserting the received data entry into the second section.

17. The method of claim 15, further comprising copying the number of data entries from the first section over to the second section.

18. The method of claim 15, further comprising updating a section pointer in the one entry of the index table to include a memory address of the second section.

19. A method comprising:

accessing an entry of an index table, the accessed entry corresponding to a hash value;

reading a valid bit in the corresponding entry of the index table; and

if the valid bit is set low,

finding a first free section of a smallest available size in a key data base having a number of sizes of sections,

allocating the first free section of the smallest available size to the corresponding entry of the index table, and

inserting a data entry into the allocated first free section of the smallest available size, wherein the data entry includes a key having the hash value.

20. The method of claim 19, wherein the smallest available size corresponds to a size capable of storing a single data entry.

21. The method of claim 19, wherein the inserted data entry includes a key and a rule.

22. The method of claim 21, wherein the inserted data entry further includes a timestamp.

23. The method of claim 19, further comprising setting the valid bit high.

24. The method of claim 19, further comprising updating a section pointer in the corresponding entry of the index table to include a memory address of the allocated first free section of the smallest available size.

25. The method of claim 19, further comprising updating a head pointer register corresponding to the smallest available size to include a memory address of another free section of the smallest available size.

26. The method of claim 19, further comprising:

if the valid bit is set high,

reading a section pointer in the corresponding entry of the index table to determine a memory address of a section of the key database previously allocated to the corresponding entry of the index table,

determining a size of the previously allocated section,

finding a first free section in the key database of a size greater than the size of the previously allocated section,

allocating the first free section of the greater size to the corresponding entry of the index table, and

inserting the data entry into the first free section of the greater size.

27. The method of claim 26, further comprising copying a data entry from the previously allocated section over to the allocated first free section of the greater size, wherein each data entry within the first free section includes a key having the same hash value.

28. The method of claim 26, further comprising updating the section pointer to include a memory address of the allocated first free section of the greater size.

29. The method of claim 26, further comprising updating a head pointer register corresponding to the greater size to include a memory address of another free section of the greater size.

30. The method of claim 26, further comprising determining the size of the previously allocated section by determining a number of valid bits set high in the corresponding entry of the index table, the number of high valid bits indicating the size of the previously allocated section.

31. A method comprising:

accessing an entry in an index table, the accessed entry corresponding to a hash value;

reading a plurality of valid bits from the corresponding entry of the index table;

determining a number of the plurality of valid bits set high;

finding in a key database a first free section of a size equal to one more than the number of high valid bits, the key database having sections of a number of sizes, each section for storing data entries, wherein each data entry within a section includes a key having the same hash value;

allocating the first free section of a size one more than the number of high valid bits to the corresponding entry of the index table; and

inserting a data entry into the allocated section of the key database.

32. The method of claim 31, further comprising:

updating a section pointer in the corresponding entry of the index table to include a memory address of the first free section of a size equal to one more than the number of high valid bits; and

setting one bit high of the plurality of valid bits in the corresponding entry of the index table.

33. The method of claim 31, further comprising updating a head pointer register corresponding to the size equal to one more than the number of high valid bits to include a memory address of another free section of the size equal to one more than the number of high valid bits.

34. The method of claim 31, wherein the inserted data entry includes a key and a rule.

35. The method of claim 34, wherein the inserted data entry further includes a timestamp.

36. The method of claim 31, wherein the number of valid bits set high is at least one, the method further comprising:

accessing the section pointer in the corresponding entry of the index table, the section pointer including a memory address of a section in the key database of a size equal to the number of high valid bits;

copying a data entry from the section of a size equal to the number of high valid bits over to the allocated section of a size equal to one more than the number of high valid bits.

37. The method of claim 36, further comprising updating a head pointer register corresponding to the size equal to the number of high valid bits to include the memory address.

38. A data structure comprising:

an index table for storing a plurality of entries, each of the entries corresponding to one of a plurality of hash values, each entry including a section pointer to identify a memory address of one of a plurality of sections of a key database and each entry including valid bits to indicate a size of the respective section of the key database,

wherein the key database is for storing a plurality of data entries, each data entry including a search key having one of the plurality of hash values, the data entries grouped into the plurality of sections, each section for storing data entries with search keys having the same hash value.

39. The data structure of claim 38, wherein the number of valid bits corresponds to a number of sizes of sections in the key database.

40. The data structure of claim 38, wherein each entry in the index table corresponds to a respective hash value of an n-bit hash function.

41. The data structure of claim 40, wherein the number of entries in the index table is equal to 2ⁿ, where n is the number of bits of the n-bit hash function.

42. The data structure of claim 38, wherein at least one of the data entries of the key database further includes a rule.

43. The data structure of claim 38, wherein at least one of the data entries of the key database further includes a timestamp.

44. The data structure of claim 38, wherein the key database is stored in a first memory and the index table is stored in a second memory.

45. The data structure of claim 38, wherein the key database and the index table are stored in a single memory.

46. The data structure of claim 38, wherein each of the key database and the index table are stored in a random access memory.

47. A method comprising:

receiving a data packet;

generating a search key based on the received data packet;

generating a hash value by applying a hash function to the generated search key;

accessing an entry in an index table, the entry corresponding to the generated hash value, wherein the entry includes a valid bit and a section pointer, the valid bit for indicating a size of a first section of a key database, the section pointer for identifying the location of the first section;

searching the first section of the key database identified by the section pointer for a search key corresponding to the generated search key;

if the first section of the key database identified by the section pointer does not contain a search key that corresponds to the generated search key,

allocating a second section of the key database, wherein the second section has a size greater than the size of the first section;

inserting the generated search key in the second section of the key database;

moving each search key of the first section to the second section of the key database.

48. The method of claim 47, further comprising updating the valid bit of the entry of the index table corresponding to the generated hash value, wherein the updated valid bit is for indicating the size of the allocated second section.

49. The method of claim 47, further comprising updating the section pointer of the entry of the index table corresponding to the generated hash value, wherein the updated section pointer is for indicating the location of the allocated second section.

50. The method of claim 47, wherein each section of the key database includes a number of search keys corresponding to a size indicated by a respective valid bit in the index table.