Tree data structure with range-specifying keys and associated methods and apparatuses

• US 20040133590A1
• Filed: 08/08/2003
• Published: 07/08/2004
• Est. Priority Date: 08/08/2002
• Status: Abandoned Application

• Current Assignee: Alex E. Henderson, Laxminarayana Tumuluru, Monis Rahman, Richard D. Trauben
• Original Assignee: Alex E. Henderson, Laxminarayana Tumuluru, Monis Rahman, Richard D. Trauben
• Inventors: Tumuluru, Laxminarayana, Trauben, Richard D., Rahman, Monis, Henderson, Alex E.
• Application Number:
  US10/637,122
• Publication Number:
  US 20040133590A1
• Time in Patent Office: Days
• US Class Current: 707/102
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees

Abstract

A tree data structure with range-specifying keys and associated methods. In one embodiment, the data structure is a tree that is stored in a machine readable medium. Each key has two values that define a range and has an associated data item that is associated with the range. Various embodiments of processes to search the tree, add ranges and keys to the tree, delete ranges and keys from the tree, and to generally maintain the tree data structure are disclosed.

Claims

1. A data structure comprising:

a root node, the root node including a number of sequential keys, each key including a first value and a second value, the first and second values of each key defining a range for that key, wherein the ranges of the number of key are non-overlapping; and

a pointer associated with the root node, the pointer identifying a child node, the child node having a range outside the range of each key in the root node.

2. The data structure of claim 1, wherein at least one of the keys of the root node further includes a data element.

3. The data structure of claim 1, wherein at least one of the keys of the root node further includes a pointer to an associated data element.

4. The data structure of claim 1, wherein the first value includes a lower bound of the range and the second value includes an upper bound of the range.

5. The data structure of claim 1, wherein one of the keys of the root node includes a pointer to a set of data elements.

6. The data structure of claim 5, wherein the set of data elements comprises a linked list.

7. The data structure of claim 5, wherein each data element of the set is associated with the range of the one key.

8. The data structure of claim 5, wherein one data element of the set is further associated with another one of the keys of the root node.

9. The data structure of claim 5, wherein the set of data elements is prioritized.

10. The data structure of claim 9, wherein a highest priority data element of the set of data elements corresponds to a data element having a longest length prefix.

11. The data structure of claim 1, further comprising a temporary node including a number of keys that is less than a minimum number of keys.

12. The data structure of claim 1, further comprising a temporary key, the temporary key having a range overlapping with the range of at least one of the keys in the root node.

13. The data structure of claim 1, wherein the range of the child node is between the ranges of two sequential keys.

14. The data structure of claim 1, wherein the range of the child node is beyond the range of an end key of the number of keys.

15. The data structure of claim 1, wherein the range of each of the keys corresponds to a range of network addresses.

16. The data structure of claim 1, wherein the root node and the child node comprise a B-Tree data structure.

17. The data structure of claim 1, wherein the data structure is capable of being stored in a machine readable medium.

18. The data structure of claim 1, wherein the machine readable medium comprises one of a memory device, a carrier wave, an optical storage device, and a magnetic storage device.

19. A method comprising:

storing in a memory a root node, the root node including a number of sequential keys, each key including a first value and a second value, the first and second values of each key defining a range for that key, wherein the ranges of the number of key are non-overlapping; and

storing in the memory a pointer associated with the root node, the pointer identifying a child node, the child node having a range outside the range of each key in the root node.

20. The method of claim 19, wherein at least one of the keys of the root node further includes a data element.

21. The method of claim 19, wherein at least one of the keys of the root node further includes a pointer to an associated data element.

22. The method of claim 19, wherein the first value includes a lower bound of the range and the second value includes an upper bound of the range.

23. The method of claim 19, wherein one of the keys of the root node includes a pointer to a set of data elements.

24. The method of claim 23, wherein the set of data elements comprises a linked list.

25. The method of claim 23, wherein each data element of the set is associated with the range of the one key.

26. The method of claim 23, wherein one data element of the set is further associated with another one of the keys of the root node.

27. The method of claim 23, wherein the set of data elements is prioritized.

28. The method of claim 27, wherein a highest priority data element of the set of data elements corresponds to a data element having a longest length prefix.

29. The method of claim 19, further comprising storing in the memory a temporary node including a number of keys that is less than a minimum number of keys.

30. The method of claim 19, further comprising storing in the memory a temporary key, the temporary key having a range overlapping with the range of at least one of the keys in the root node.

31. The method of claim 19, wherein the range of the child node is between the ranges of two sequential keys.

32. The method of claim 19, wherein the range of the child node is beyond the range of an end key of the number of keys.

33. The method of claim 19, wherein the number of sequential keys are stored in contiguous memory locations of the memory.

34. An apparatus comprising:

a memory having a data structure stored therein, the data structure including

a root node, the root node including a number of sequential keys, each key including a first value and a second value, the first and second values of each key defining a range for that key, wherein the ranges of the number of key are non-overlapping, and

a pointer associated with the root node, the pointer identifying a child node, the child node having a range outside the range of each key in the root node.

35. The apparatus of claim 34, wherein at least one of the keys of the root node further includes a data element.

36. The apparatus of claim 34, wherein at least one of the keys of the root node further includes a pointer to an associated data element.

37. The apparatus of claim 34, wherein the first value includes a lower bound of the range and the second value includes an upper bound of the range.

38. The apparatus of claim 34, wherein one of the keys of the root node includes a pointer to a set of data elements.

39. The apparatus of claim 38, wherein the set of data elements comprises a linked list.

40. The apparatus of claim 38, wherein each data element of the set is associated with the range of the one key.

41. The apparatus of claim 38, wherein one data element of the set is further associated with another one of the keys of the root node.

42. The apparatus of claim 38, wherein the set of data elements is prioritized.

43. The apparatus of claim 42, wherein a highest priority data element of the set of data elements corresponds to a data element having a longest length prefix.

44. The apparatus of claim 34, further comprising a temporary node stored in the memory, the temporary node including a number of keys that is less than a minimum number of keys.

45. The apparatus of claim 34, further comprising a temporary key stored in the memory, the temporary key having a range overlapping with the range of at least one of the keys in the root node.

46. The apparatus of claim 34, wherein the range of the child node is between the ranges of two sequential keys.

47. The apparatus of claim 34, wherein the range of the child node is beyond the range of an end key of the number of keys.

48. The apparatus of claim 34, further comprising a processing device coupled with the memory.

49. The apparatus of claim 48, wherein the processing device includes logic to generate the data structure.

50. The apparatus of claim 48, further comprising a set of instructions stored in the memory that, when executed on the processing device, generate the data structure in the memory.

51. The apparatus of claim 48, wherein the processing device includes a set of instructions stored thereon that, when executed on the processing device, generate the data structure in the memory.

52. An article of manufacture comprising:

a machine accessible medium providing content that, when accessed by a machine, causes the machine to

store in a memory a root node, the root node including a number of sequential keys, each key including a first value and a second value, the first and second values of each key defining a range for that key, wherein the ranges of the number of key are non-overlapping; and

store in the memory a pointer associated with the root node, the pointer identifying a child node, the child node having a range outside the range of each key in the root node.

53. The article of manufacture of claim 52, wherein at least one of the keys of the root node further includes a data element.

54. The article of manufacture of claim 52, wherein at least one of the keys of the root node further includes a pointer to an associated data element.

55. The article of manufacture of claim 52, wherein the first value includes a lower bound of the range and the second value includes an upper bound of the range.

56. The article of manufacture of claim 52, wherein one of the keys of the root node includes a pointer to a set of data elements.

57. The article of manufacture of claim 56, wherein the set of data elements comprises a linked list.

58. The article of manufacture of claim 56, wherein each data element of the set is associated with the range of the one key.

59. The article of manufacture of claim 56, wherein one data element of the set is further associated with another one of the keys of the root node.

60. The article of manufacture of claim 56, wherein the set of data elements is prioritized.

61. The article of manufacture of claim 60, wherein a highest priority data element of the set of data elements corresponds to a data element having a longest length prefix.

62. The article of manufacture of claim 52, wherein the content, when accessed, further causes the machine to store in the memory a temporary node including a number of keys that is less than a minimum number of keys.

63. The article of manufacture claim 52, wherein the content, when accessed, further causes the machine to store in the memory a temporary key, the temporary key having a range overlapping with the range of at least one of the keys in the root node.

64. The article of manufacture of claim 52, wherein the range of the child node is between the ranges of two sequential keys.

65. The article of manufacture of claim 52, wherein the range of the child node is beyond the range of an end key of the number of keys.

66. The article of manufacture of claim 52, wherein the number of sequential keys are stored in contiguous memory locations of the memory.