Apparatus and method for searching a n-branch data structure using information in entries

• US 7,272,611 B1
• Filed: 10/20/2003
• Issued: 09/18/2007
• Est. Priority Date: 10/28/2002
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: Network Appliance Incorporated (NetApp, Inc.)
• Inventors: Cuppett, Jeff, Leong, Reynold
• Primary Examiner(s): Gaffin; Jeffrey
• Assistant Examiner(s): Wu; Yicun
• Application Number:
  US10/690,244
• Time in Patent Office: 1,429 Days
• Field of Search: 707 1- 10, 707100-1041, 707200-206, 370/392, 370/389, 370/412
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9014 hash tables
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• 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

Abstract

Techniques for searching a data structure using information in entries found in the data structure are provided. A key is determined for an entry in a data structure and an entry for that key is accessed. It is determined if that entry is the correct entry for the key. If not, information in the entry is used to determine a second entry for the key. It is then determined if the second entry is the correct entry for the key. If not, the process continues as described above until the correct entry is found.

Claims

1. A method for searching a data structure, the method comprising:

hashing a search key to generate a hash result;

determining a first entry in a plurality of entries in the data structure using the hash result;

determining if the first entry corresponds to the search key;

if the first entry does not correspond to the search key, using information in the first entry to determine a second entry in the data structure, the second entry included in a branch of a plurality of branches associated with the first entry;

if the first entry does correspond to the search key, performing an action on information stored in the first entry.

2. The method of claim 1, further comprising:

determining if the second entry corresponds to the search key; and

if the second entry does not correspond to the search key, using information in the second entry to determine a third entry in the data structure, the third entry included in a branch of a plurality of branches associated with the second entry.

3. The method of claim 2, further comprising if the second entry does correspond to the search key, performing an action associated with the second entry.

4. The method of claim 2, wherein using the information in the first entry to determine the second entry comprises comparing the information in the first entry to at least a first part of the search key to determine if the information in the first entry matches the at least the first part of the search key.

5. The method of claim 4, wherein using the information in the second entry to determine the third entry comprises comparing the information in the second entry to at least a second part of the search key to determine if the information in the second entry matches the at least the second part of the search key, the at least the second part of the search key being different than the at least a first part of the search key.

6. The method of claim 1, wherein determining if the first entry corresponds to the search key comprises comparing an entry key in the entry to the search key to determine if the first entry matches to the search key.

7. The method of claim 1, wherein the information is used to determine which branch in the plurality of branches associated with the first entry to search in for the second entry.

8. The method of claim 1, wherein performing the action comprises at least one of retrieving information from the first entry, updating information in the first entry, and deleting information in the first entry.

9. The method of claim 1, wherein the information comprises a plurality of hints, wherein a hint in the plurality of hints corresponds to information associated with the search key and points to the second entry.

10. The method of claim 9, wherein each hint is associated with a branch in the plurality of branches associated with the first entry.

11. A method for searching a data structure, the method comprising:

(a) hashing a search key to generate a hash result;

(b) determining an entry in a plurality of entries in the data structure using the hash result;

(c) determining if an entry key in the entry corresponds to the search key;

(d) if the entry key does not correspond to the search key, repeating step (c) using a subsequent entry until the entry key from the subsequent entry corresponds to the search key, wherein the subsequent entry is determined using information in the entry, wherein as step (c) is repeated using a first subsequent entry and a second subsequent entry, different information in the search key is used to determine the second subsequent entry than was used in determining the first subsequent entry; and

(e) if the entry key does correspond to the search key, performing an action on information stored in the entry.

12. The method of claim 11, wherein the subsequent entry is determined by comparing information in the search key to information in the entry to determine if the information in the search key matches the information in the entry.

13. The method of claim 11, wherein performing the action comprises at least one of retrieving information from the first entry, updating information in the first entry, and deleting information in the first entry.

14. The method of claim 11, wherein the information comprises a plurality of hints, wherein a hint in the plurality of hints corresponds to information associated with the key and points to the subsequent entry.

15. The method of claim 14, wherein each hint is associated with a branch in one or more branches associated with the entry.

16. A method for searching for an entry in a plurality of entries in a data structure, the method comprising:

receiving a data frame from a storage network;

determining a search key for the data structure using information in the data frame;

hashing the search key to generate a hash result;

determining a first entry in the plurality of entries corresponding to the hash result;

determining if the first entry corresponds to the search key;

if the first entry does not correspond to the search key, comparing information in the first entry with a first part of the search key to determine a second entry in the data structure, the second entry included in a branch of a plurality of branches associated with the first entry; and

if the first entry corresponds to the search key, retrieving an address for a storage device found in the first entry.

17. The method of claim 16, further comprising:

determining if the second entry corresponds to the search key; and

if the second entry does not correspond to the key, comparing information in the second entry with a second part of the search key to determine a third entry in the data structure, the third entry included in a branch of a plurality of branches associated with the second entry.

18. The method of claim 17, further comprising writing the address to the data frame, wherein the address is used to perform an action with the storage device at the address.

19. The method of claim 18, wherein the action comprising at least one of writing, erasing, and updating information at the address in the storage device using information in the data frame.

20. A machine-readable medium having instructions which, when executed, cause a machine to perform a process, the process comprising:

(a) hashing a search key to generate a hash result;

(b) determining an entry in a plurality of entries in the data structure using the hash result;

(c) determining if an entry key in the entry corresponds to the search key;

(d) if the entry key does not correspond to the search key, repeating step (c) using a subsequent entry until the entry key from the subsequent entry corresponds to the search key, wherein the subsequent entry is determined using information in the entry, wherein as step (c) is repeated using a first subsequent entry and a second subsequent entry, different information in the search key is used to determine the second subsequent entry than was used in determining the first subsequent entry; and

(e) if the entry key does correspond to the search key, performing an action associated with the entry.

21. The machine-readable medium of claim 20, wherein the subsequent entry is determined by comparing information in the search key to information in the entry to determine if the information in the search key matches the information in the entry.

22. The machine-readable medium of claim 20, wherein performing the action comprises at least one of retrieving information from the first entry, updating information in the first entry, and deleting information in the first entry.

23. The machine-readable medium of claim 20, wherein the information comprises a plurality of hints, wherein a hint in the plurality of hints corresponds to information associated with the key and points to the subsequent entry.

24. The machine-readable medium of claim 23, wherein each hint is associated with a branch in one or more branches associated with the entry.