Use of dynamic multi-level hash table for managing hierarchically structured information

• US 7,058,639 B1
• Filed: 08/30/2002
• Issued: 06/06/2006
• Est. Priority Date: 04/08/2002
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Joshi, Sameer, Chatterjee, Surojit
• Primary Examiner(s): Alam, Shahid
• Assistant Examiner(s): FLEURANTIN, JEAN B
• Application Number:
  US10/232,907
• Time in Patent Office: 1,376 Days
• Field of Search: 707 1- 10, 707100-1041, 707200-206, 711/113, 711118-119, 711/216, 711/213, 711218-219
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: Y10S 707/99931 Database or file accessing

Abstract

An aspect of the invention provides a method for managing information associated with a hierarchical key. A plurality of hash tables are created for a plurality of levels of a hierarchy associated with a hierarchical key, wherein each hash table is associated with a corresponding level of the hierarchy. Entries are stored within each of the plurality of hash tables, wherein the entries are associated with key names that have as many levels as the level associated with the respective hash table. Furthermore, a reference to a descendant entry that is in a respective hash table may be stored within each entry.

Claims

1. A method for managing hierarchically structured information, the method comprising:

creating a plurality of hash tables based on a composite key, wherein key values associated with the composite key are hierarchically related based on multiple levels;

wherein each hash table corresponds to a particular level of the multiple levels; and

storing, within each of the plurality of hash tables, entries that are associated with key values that have as many levels as the particular level that corresponds to the respective hash table.

2. The method of claim 1 comprising:

storing within each entry a reference to a descendant entry, if any, that is in a respective hash table of the plurality of hash tables.

3. The method of claim 1 comprising:

storing the plurality of hash tables in a cache.

4. The method of claim 3 comprising:

maintaining a counter, for each entry, of a number of times that the respective entry is accessed;

determining which entry is least frequently accessed based on the counters for the entries;

deleting the entry that is least frequently accessed.

5. The method of claim 1 comprising:

creating a hash table index for identifying the location of each of the plurality of hash tables.

6. The method of claim 1, comprising:

creating a hash table array for storing the plurality of hash tables;

creating a hash table array index for the hash table array, and

using the hash table array index to identify the location of a hash table of the plurality of hash tables in the hash table array.

7. The method of claim 1 comprising:

dynamically allocating memory for a hash table of the plurality of hash tables upon meeting a specified condition associated with the hash table.

8. The method of claim 1 comprising:

dynamically deallocating memory for a hash table of the plurality of hash tables upon meeting a specified condition associated with the hash table.

9. The method of claim 1, wherein the key values are names associated with respective name-value pairs and the managed information are values associated with the respective name-value pairs, and wherein the steps of creating and storing are based on the name-value pairs.

10. The method of claim 9, wherein the value of at least one of the name-value pairs is null, and wherein the steps of creating and storing are based on the name-value pairs.

11. The method of claim 9, wherein the names of the name-value pairs are Universal Resource locators and the values of the name-value pairs are content associated with a respective Universal Resource Locator.

12. The method of claim 1 comprising:

storing the plurality of hash tables in a cluster repository.

34. The method of claim 1, wherein each hash table corresponds to only one particular level of the multiple levels and no two hash tables correspond to the same particular level of the multiple levels.

13. A method for managing hierarchically structured information, the method comprising:

determining how many levels exist in a particular key name;

creating a respective hash table for each level of the particular key name for which a hash table has not yet been created;

computing a hash key for each key component of the particular key name; and

storing entries in the hash tables that correspond to key components that correspond to each level of the particular key name, wherein the location of each entry in a respective hash table is identified by a respective hash key.

14. A method for locating hierarchically structured information, the method comprising:

determining how many levels exist in a particular key name of a key domain;

locating a particular hash table from a plurality of hash tables, wherein each of the plurality of hash tables corresponds to a particular level of a hierarchy of the key domain, wherein the Particular hash table corresponds to the number of levels that exist in the particular key name;

computing a hash key for the particular key name; and

locating in the particular hash table, based on the hash key, an entry associated with the particular key name.

15. A method for deleting hierarchically structured information, the method comprising:

determining how many levels exist in a particular key name of a key domain;

locating a particular hash table from a plurality of hash tables, wherein each of the plurality of hash tables corresponds to a particular level of a hierarchy of the key domain, wherein the particular hash table corresponds to the number of levels that exist in the particular key name;

computing a hash key for the particular key name;

locating in the particular hash table, based on the hash key, an entry associated with the particular key name; and

deleting the entry associated with the particular key name.

16. A method for recursively deleting hierarchically structured information, the method comprising:

determining how many levels exist in a particular key name of a key domain;

locating a first hash table from a plurality of hash tables, wherein each of the plurality of hash tables corresponds to a particular level of a hierarchy of the key domain, wherein the particular hash table corresponds to the number of levels that exist in the particular key name;

computing a hash key for the particular key name;

locating in the first hash table, based on the hash key, a first entry associated with the particular key name;

using one or more references from the first entry to locate descendant entries of the particular key name in respective hash tables of the plurality of hash tables; and

deleting the first entry and the descendant entries.

17. A method for locating information associated with a second key name that is a child of a first key name in a hierarchy, the method comprising:

locating, based on the first key name, a first entry in a first hash table, wherein the first entry is associated with the first key name;

reading, from the first entry, information that identifies a location of a second entry associated with the second key name, wherein the location is in a second hash table different from the first hash table; and

locating the second entry in the second hash table based on the information that identifies the location of the second entry.

18. A computer-readable medium carrying one or more sequences of instructions for managing hierarchically structured information, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

creating a plurality of hash tables based on a composite key, wherein key values associated with the composite key are hierarchically related based on multiple levels;

wherein each hash table corresponds to a particular level of the multiple levels; and

storing, within each of the plurality of hash tables, entries that are associated with key values that have as many levels as the particular level that corresponds to the respective hash table.

19. The computer-readable medium of claim 18 wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the step of:

storing within each entry a reference to a descendant entry, if any, that is in a respective hash table of the plurality of hash tables.

20. The computer-readable medium of claim 18 wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the step of:

storing the plurality of hash tables in a cache.

21. The computer-readable medium of claim 20 wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the step of:

maintaining a counter, for each entry, of a number of times that the respective entry is accessed;

determining which entry is least frequently accessed based on the counters for the entries;

deleting the entry that is least frequently accessed.

22. The computer-readable medium of claim 18 wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the step of:

creating a hash table index for identifying the location of each of the plurality of hash tables.

23. The computer-readable medium of claim 18 wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the step of:

creating a hash table array for storing the plurality of hash tables;

creating a hash table array index for the hash table array, and

using the hash table array index to identify the location of a hash table of the plurality of hash tables in the hash table array.

24. The computer-readable medium of claim 18 wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the step of:

dynamically allocating more memory for a hash table of the plurality of hash tables upon meeting a specified condition associated with the hash table.

25. The computer-readable medium of claim 18, wherein the key values are names associated with respective name-value pairs and the managed information are values associated with the respective name-value pairs, and wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of creating and storing based on the name-value pairs.

26. The computer-readable medium of claim 25, wherein at least one value of the name-value pairs is null, and wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of creating and storing based on the name-value pairs.

27. The computer-readable medium of claim 25, wherein the names of the name-value pairs are Universal Resource Locators and the values of the name-value pairs are content associated with a respective Universal Resource Locator, and wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of creating and storing based on the name-value pairs.

28. The computer-readable medium of claim 18 wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the step of:

storing the plurality of hash tables in a cluster repository.

29. A computer-readable medium carrying one or more sequences of instructions for managing hierarchically structured information, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

determining how many levels exist in a particular key name;

creating a respective hash table for each level of the particular key name for which a hash table has not yet been created;

computing a hash key for each key component of the particular key name; and

storing entries in the hash tables that correspond to each level of the particular key name, wherein the location of each entry in a respective hash table is identified by a respective hash key.

30. A computer-readable medium carrying one or more sequences of instructions for locating hierarchically structured information, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

determining how many levels exist in a particular key name of a key domain;

locating a particular hash table from a plurality of hash tables, wherein each of the plurality of hash tables corresponds to a particular level of a hierarchy of the key domain, wherein the particular hash table corresponds to the number of levels that exist in the particular key name;

computing a hash key for the particular key name; and

locating in the particular hash table, based on the hash key, an entry associated with the particular key name.

31. A computer-readable medium carrying one or more sequences of instructions for deleting hierarchically structured information, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

determining how many levels exist in a particular key name of a key domain;

locating a particular hash table from a plurality of hash tables, wherein each of the plurality of hash tables corresponds to a particular level of a hierarchy of the key domain, wherein the particular hash table corresponds to the number of levels that exist in the particular key name;

computing a hash key for the particular key name;

locating in the particular hash table, based on the hash key, an entry associated with the particular key name; and

deleting the entry associated with the particular key name.

32. A computer-readable medium carrying one or more sequences of instructions for recursively deleting hierarchically structured information, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

determining how many levels exist in a particular key name of a key domain;

locating a first hash table from a plurality of hash tables, wherein each of the plurality of hash tables corresponds to a particular level of a hierarchy of the key domain, wherein the particular hash table corresponds to the number of levels that exist in the particular key name;

computing a hash key for the particular key name;

locating in the first hash table, based on the hash key, a first entry associated with the particular key name;

using one or more references from the first entry to locate descendant entries of the particular key name in respective hash tables of the plurality of hash tables; and

deleting the first entry and the descendant entries.

33. A computer-readable medium carrying one or more sequences of instructions for locating information associated with a second key name that is a child of a first key name in a hierarchy, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

locating, based on the first key name, a first entry in a first hash table, wherein the first entry is associated with the first key name;

reading, from the first entry, information that identifies a location of a second entry associated with the second key name, wherein the location is in a second hash table different from the first hash table; and

locating the second entry in the second hash table based on the information that identifies the location of the second entry.