Tiered hashing for data access

• US 6,516,320 B1
• Filed: 03/08/1999
• Issued: 02/04/2003
• Est. Priority Date: 03/08/1999
• Status: Expired due to Term

• Current Assignee: Tumbleweed Holdings LLC (Equitable IP Corporation)
• Original Assignee: Pliant Technologies, Inc. (RDE, Inc.)
• Inventors: Odom, Paul S., Massey, Michael J.
• Primary Examiner(s): Alam, Hosain T.
• Assistant Examiner(s): Nguyen, Tam V
• Application Number:
  US09/264,298
• Time in Patent Office: 1,429 Days
• Field of Search: 707/1, 707/2, 707/10, 707/8, 707/100, 707/101, 707/7, 707/3, 707/4
• US Class Current: 707/747
• CPC Class Codes: G06F 16/902 using more than one table in sequence, i.e. systems with three or more layers
• CPC Class Codes: Y10S 707/99937 Sorting
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A memory for access by a program being executed by a programmable control device includes a data access structure stored in the memory, the data access structure including a first and a second index structure (each having a plurality of entries) together forming a tiered index. At least one entry in the first structure indicates an entry in the second structure. The number of entries in the second structure being dynamically changeable. A method for building a tiered index structure includes building a first-level index structure having a predetermined number of entries, building a second-level index structure having a dynamic number of entries, and establishing a link between an entry in the first-level index structure and an entry in the second-level index structure.

Claims

1. A memory for access by an application program being executed on a programmable control device, comprising:

a data access hash structure stored in said memory, said data access hash structure including a first a second a third and a fourth index structure together forming a tiered hash index;

said first structure including a plurality of entries, at least one of said plurality of entries indicating a unique entry in said second structure;

said second structure having a plurality of entries, at least one of said plurality of entries indicating a unique entry in said third structure;

said third structure having a plurality of entries, at least one of said plurality of entries indicating a unique entry in said fourth structure; and

said fourth structure having a plurality of entries.

2. The memory of claim 1, wherein the plurality of entries of the first structure comprise a fixed number of entries and the plurality of entries of the second structure comprise a dynamically changeable number of entries.

3. The memory of claim 1, wherein the first structure comprises a linked list structure.

4. The memory of claim 3, wherein an entry in said first structure comprises:

an identifier attribute;

a next first structure entry indicator attribute; and

a second structure entry indicator attribute.

5. The memory of claim 4, wherein an entry in said first structure further comprises an overflow indicator attribute.

6. The memory of claim 5, wherein said overflow indicator attribute indicates an overflow structure comprising a plurality of entries, at least one of said plurality of entries having an identifier attribute and a pointer attribute.

7. The memory of claim 6, wherein each of the plurality of entries in the overflow structure are ordered within the overflow structure in accordance with a value associated with each of said entries identifier attribute.

8. The memory of claim 1, wherein the second structure comprises a linked list structure.

9. The memory of claim 1, wherein an entry of said second structure comprises:

an identifier attribute; and

a next second structure entry indicator attribute.

10. The memory of claim 9, wherein an entry in said second structure further comprises an overflow indicator attribute.

11. The memory of claim 10, wherein said overflow indicator attribute indicates an overflow structure comprising a plurality of entries, at least one of said plurality of entries having an identifier attribute and a pointer attribute.

12. The memory of claim 11, wherein each of the plurality of entries in the overflow structure are ordered within the overflow structure in accordance with a value associated with each of said entries identifier attribute.

13. The memory of claim 1, wherein the number of entries in said third structure is dynamically changeable and related to the number of entries in said second structure.

14. The memory of claim 13, wherein the third structure comprises a linked list structure.

15. The memory of claim 13, wherein an entry in said third structure comprises:

a data object location attribute;

a status attribute; and

a next third structure. entry indicator attribute.

16. The memory of claim 15, wherein the data object location attribute comprises:

a data object file identifier portion; and

a data object offset portion.

17. A method for building a tiered hash index structure, comprising:

building a first-level hash index structure having a predetermined number of entries;

building a second level hash index structure;

building a third-level hash index structure;

building a fourth-level hash index structure;

establishing a link between an entry in the first-level index structure and a unique entry in the second-level index structure;

establishing a link between an entry in the second-level index structure and a unique entry in the third-level index structure; and

establishing a link between an entry in the third-level index structure and a unique entry in the fourth-level index structure.

18. The method of claim 17, wherein the act of building a first level hash index structure comprises building a link-list hash structure.

19. The method of claim 17, wherein the act of building a second-level hash index structure comprises building a variable-length hash structure.

20. The method of claim 19 wherein the act of building a second-level hash index structure comprises building a link-list hash structure.

21. The method of claim 17, further comprising establishing a link between an entry in the fourth-level hash index structure and a data object.

22. The method of claim 21, further comprising:

receiving an object identifier;

identifying an entry in said first-level hash index structure based on the object identifier;

identifying an entry in said second-level hash index structure based on the identified entry in said first-level hash index structure;

identifying an entry in said third-level hash index structure based on the identified entry in said second-level hash index structure; and

identifying an entry in said fourth-level hash index structure based on the identified entry in said second-level hash index structure.

23. The method of claim 22, further comprising retrieving a data object indicated by the identified entry in said fourth-level hash index structure.

24. The method of claim 23, wherein the act of retrieving a data object comprises using a location component, where a first portion of said location component indicates a file, and a second portion of said location component indicates an offset into the file.

25. The method of claim 24, wherein the first portion of said location component comprises a 1-byte field, and the second portion of said location component comprises a 4-byte field.

26. The method of claim 22, wherein the act of receiving an object identifier comprises receiving a numeric identifier.

27. The method of claim 22, wherein the act of receiving an object identifier comprises receiving an alphanumeric identifier.

28. The method of claim 22, wherein the act of identifying an entry in said second-level hash index structure comprises traversing a link between the identified first-level hash index structure entry and an entry in said second-level hash index structure.

29. The method of claim 22, wherein the act of identifying an entry in said second-level hash index structure comprises:

identifying a first entry in said second-level hash index structure based on the identified entry in said first-level hash index structure; and

traversing said second-level hash index structure beginning at the identified first entry and comparing the object identifier with a portion of each entry traversed during the act of traversing said second-level hash index structure.

30. The method of claim 22, further comprising

building an overflow structure;

and

establishing a link between the overflow structure and an entry in the second-level hash index structure.

31. The method of claim 30, wherein the act of identifying an entry in said second-level hash index structure uses the overflow structure.

32. The method of claim 17, wherein the act of building a third-level hash index structure comprises building a link-list hash structure.

33. The method of claim 17, wherein the act of identifying an entry in said third-level hash index structure comprises traversing a link between the identified second-level hash index structure entry and an entry in said third-level index structure.

34. The method of claim 17, wherein the act of identifying an entry in said third-level hash index structure comprises:

identifying a first entry in said third-level hash index structure based on the identified entry in said second-level hash index structure; and

traversing said third-level hash index structure beginning at the identified first entry and comparing the object identifier with a portion of each entry traversed during the act of traversing said third-level hash index structure.

35. The method of claim 17, further comprising:

building an overflow structure; and

establishing a link between the overflow structure and an entry in the second-level hash index structure and an entry in the third-level hash index structure.

36. The method of claim 35, wherein the act of building said overflow structure comprises building an ordered hash structure.

37. The method of claim 35, wherein the act of identifying an entry in said third-level hash index structure uses the overflow structure.

52. The method of claim 17, wherein the act of building said fourth-level hash index structure comprises building a link-list structure.

53. The program storage device of claim 17, wherein the instructions to build said fourth-level hash index structure comprise instructions to build a link-list structure.

54. The method of claim 22, wherein the act of identifying an entry in said fourth-level hash index structure comprises:

identifying a first entry in said fourth-level hash index structure based on the identified entry in said third-level hash index structure; and

traversing said fourth-level hash index structure beginning at the identified first entry and comparing the object identifier with a portion of each entry traversed during the act of traversing said fourth-level hash index structure.

55. The method of claim 54, further comprising

building an overflow structure;

and

establishing a link between the overflow structure and an entry in the third-level hash index structure and an entry in the fourth-level hash index structure.

56. The method of claim 55, wherein the act of building said overflow structure comprises building an ordered hash structure.

57. The method of claim 55, wherein the act of identifying the first entry in said fourth-level hash index structure uses the overflow structure.

38. A program storage device, readable by a programmable control device, comprising instructions stored on the program storage device for causing the programmable control device to build a tiered hash index structure, including instructions to:

build a first-level hash index structure having a predetermined number of entries;

build a second-level hash index structure;

a build a third-level hash index structure;

a build a fourth-level hash index structure;

to establish a link between an entry in the first-level hash index structure and a unique entry in the second-level hash index structure;

establish a link between an entry in the second-level hash index structure and a unique entry in the third-level hash index structure; and

establish a link between an entry in the third-level hash index structure and a unique entry in the fourth-level hash index structure.

39. The program storage device of claim 38, wherein the instructions to build a second-level hash index structure comprise instructions to build a variable-length hash structure.

40. The program storage device of claim 38, further comprising instructions to:

receive an object identifier;

identify an entry in said first-level hash index structure based on the object identifier;

identify an entry in said second-level hash index structure based on the identified entry in said first-level hash index structure;

identify an entry in said third-level hash index structure based on the identified entry in said second-level hash index structure; and

identify an entry in said fourth-level hash index structure based on the identified entry in said second-level hash index structure.

41. The program storage device of claim 40, further comprising instructions to retrieve a data object indicated by the identified entry in said fourth-level hash index structure.

42. The program storage device of claim 40, wherein the instructions to receive an object identifier comprise instructions to receive a numeric identifier.

43. The program storage device of claim 40, wherein the instructions to receive an object identifier comprise instructions to receive an alphanumeric identifier.

44. The program storage device of claim 40, wherein the instructions to identify an entry in said second-level hash index structure comprise instructions to:

identify a first entry in said second-level hash index structure based on the identified entry in said first-level hash index structure;

traverse said second-level hash index structure beginning at the identified first entry; and

identify a second entry in said second-level hash index structure based on the object identifier.

45. The program storage device of claim 44, wherein the instructions to identify the second entry in said second-level hash index structure comprise instructions to compare the object identifier with a portion of each entry traversed during the act of traversing said second-level hash index structure.

46. The program storage device of claim 40, wherein the instructions to identify an entry in said third-level hash index structure comprise instructions to:

identify a first entry in said third-level hash index structure based on the identified entry in said second-level hash index structure;

traverse said third-level hash index structure beginning at the identified first entry; and

identify a second entry in said third-level hash index structure based on the object identifier.

47. The program storage device of claim 46, wherein the instructions to identify the first entry in said third-level hash index structure comprise instructions to traverse a link between the identified second-level hash index structure entry and an entry in said third-level hash index structure.

48. The program storage device of claim 47, wherein the instructions to identify the second entry in said third-level hash index structure comprise instructions to compare the object identifier with a portion of each entry traversed during the act of traversing said third-level hash index structure.

49. The program storage device of claim 46, further comprising instructions to:

build an overflow structure; and

establish a link between the overflow structure and an entry in the second-level hash index structure and an entry in the third-level hash index structure.

50. The program storage device of claim 49, wherein the instructions to build said overflow structure comprise instructions to build an ordered hash structure.

51. The program storage device of claim 49, wherein the instructions to identify a first entry in said third-level hash index structure comprise instructions to use the overflow structure.

58. The program storage device of claim 40, wherein the instructions to identify an entry in said fourth-level hash index structure comprise instructions to:

identify a first entry in said fourth-level hash index structure based on the identified entry in said third-level hash index structure; and

traverse said fourth-level hash index structure beginning at the identified first entry and comparing the object identifier with a portion of each entry traversed during the act of traversing said fourth-level hash index structure.