Method and data structure for a low memory overhead database

• US 20060122989A1
• Filed: 01/25/2006
• Published: 06/08/2006
• Est. Priority Date: 03/20/2002
• Status: Active Grant

• Current Assignee: Miguel A. Guerrero, Sreenath Kurupati
• Original Assignee: Miguel A. Guerrero, Sreenath Kurupati
• Inventors: Kurupati, Sreenath, Guerrero, Miguel A.
• Granted Patent: US 7,467,151 B2
• Time in Patent Office: Days
• 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

A data structure for use in database applications. The data structure includes a key database that is searchable via an index table.

Claims

1. A method comprising:

applying a hash function to a search key to create a hash value;

accessing an entry in an index table corresponding to the hash value, the corresponding entry of the index table including a valid bit and a section pointer;

if the valid bit is set high, accessing a section of a key database identified by the section pointer, the accessed section including a number of data entries; and

comparing the data entries contained in the accessed section with the search key.

2. The method of claim 1, further comprising:

if one of the data entries contains a key matching the search key, accessing the one data entry.

3. The method of claim 2, further comprising:

accessing a rule contained in the one data entry; and

applying the rule to a packet associated with the search key.

4. The method of claim 1, wherein the corresponding entry includes a number of valid bits equal to a number of sizes of sections of the key database, the act of accessing a section of a key database further comprising accessing a section having a size corresponding to the number of valid bits set high.