Method and data structure for a low memory overhead database

• US 7,467,151 B2
• Filed: 01/25/2006
• Issued: 12/16/2008
• 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:
  US11/339,247
• Publication Number:
  US 20060122989A1
• Time in Patent Office: 1,056 Days
• Field of Search: 707/3, 707/4, 707/6, 707/100, 707/101, 707/102, 707/103.R, 707/104.1, 711/216
• 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;

accessing a section of a key database identified by the section pointer based at least in part on the valid bit, 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 farther comprising accessing a section having a size corresponding to the number of valid bits set high.