Indexing stored data

• US 7,761,474 B2
• Filed: 06/30/2004
• Issued: 07/20/2010
• Est. Priority Date: 06/30/2004
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP AG (SAP SE)
• Inventors: Booss, Daniel, Lock, Hendrik C. R.
• Primary Examiner(s): Rones; Charles
• Assistant Examiner(s): Mahmood; Rezwanul
• Application Number:
  US10/881,709
• Publication Number:
  US 20060004715A1
• Time in Patent Office: 2,211 Days
• Field of Search: 707/3, 707/5, 707/100, 707/101, 707/102
• US Class Current: 707/797
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: Y10S 707/956 Hierarchical

Abstract

Methods and apparatus, including computer program products, for providing a data structure, embodied in a computer-readable medium, implementing a tree of nodes having inner nodes and leaf nodes, and performing a scan of the data structure to identify an entry that satisfies a search criterion. Each leaf node includes a key having a first value representing a starting point of an interval, a second value representing an ending point of an interval, and a third value representing a duration of an interval. Each inner node is a root node of a subtree. Each inner node includes a key having a first value representing a minimum of the starting points of intervals in the corresponding subtree, a second value representing a maximum of the ending points of the intervals in the corresponding subtree, and a third value representing a maximum duration of the intervals in the corresponding subtree.

Claims

1. A computer program product, tangibly embodied in a computer readable storage medium, the computer program product to cause a data processing apparatus to:

provide a data structure embodied in a computer-readable medium, the data structure implementing a tree of nodes having a plurality of inner nodes and a plurality of leaf nodes,

each leaf node including a key having a first value representing a starting point of an interval, a second value representing an ending point of the interval, and a third value representing a duration of the interval, and

each inner node being a root node of a subtree, each inner node including a second key having a first value representing a minimum of the starting points of different intervals in the corresponding subtree, a second value representing a maximum of the ending points of the different intervals in the corresponding subtree, and a third value representing a duration of the longest single interval selected from the different intervals in the corresponding subtree.

2. The computer program product of claim 1, wherein each node includes one or more entries, each entry comprising:

a pointer to a record in a database table, the record defining a particular interval, a first value representing a starting point of the particular interval, a second value representing an ending point of the particular interval, and a third value representing a duration of the particular interval;

or

a pointer to a child node, a first value representing a minimum of the starting points of different intervals in a subtree having the child node as a root node of the subtree, a second value representing a maximum of the ending points of the different intervals in the subtree having the child node as the root node of the subtree, and a third value representing a duration of the longest single interval selected from the different intervals in the subtree having the child node as the root node of the subtree.

3. The computer program product of claim 2, wherein each record defines an interval representing an available slot in a capacity profile of a resource.

4. The computer program product of claim 2, further comprising instructions to:

perform a scan of the data structure to identify an entry that satisfies a search criterion.

5. The computer program product of claim 4, further comprising instructions to:

schedule an activity in at least a portion of an interval associated with the identified entry.

6. The computer program product of claim 5, further comprising instructions to:

generate a second entry based at least in part on the identified entry, delete the identified entry, or change a value of the identified entry.

7. The computer program product of claim 4, wherein the search criterion comprises one or more of a duration of a query, an earliest starting point of a query interval, a latest starting point of the query interval, an earliest ending point of the query interval, a latest ending point of the query interval, and a search direction.

8. The computer program product of claim 4, wherein the search criterion comprises a duration of a query, a starting point of a query interval and a forward search direction, and wherein instructions to perform the scan comprise instructions to:

traverse a leftmost path from a root node of the tree through one or more nodes to identify an entry that satisfies the search criterion.

9. The computer program product of claim 8, wherein instructions to traverse the leftmost path comprise instructions to:

scan a node by;

identifying the entries in the node of a first duration, and having a second value greater than or equal to the starting point of the query interval;

selecting, from among the identified entries in the node, the entry having the smallest of the second values; and

if the selected entry includes a pointer to a record in a database table, determining whether the interval of the selected entry satisfies the slot search criterion, and if so, identifying the selected entry as satisfying the search criterion, and

if the selected entry includes a pointer to a child node, traversing a path downwards to the child node, and repeating the scanning at the child node.

10. The computer program product of claim 9, wherein if none of the entries in the node are of said first duration and have a second value greater than or equal to the starting point of the query interval, the computer program product further comprises instructions to:

traverse a shortest direct path upwards, from the node towards the root node of the tree, through one or more ancestor nodes to identify one or more entries of an ancestor node having a first value greater than or equal to the starting point of the query interval and a third value greater than or equal to the duration of the query;

select, from among the identified entries in the ancestor node, the entry having the smallest of the first values; and

if the selected entry includes a pointer to a record in a database table, determine whether the interval of the selected entry satisfies the slot search criterion, and if so, identify the selected entry as satisfying the search criterion, and

if the selected entry includes a pointer to a child node, traverse a path downwards to the child node, and repeat the scanning at the child node.

11. The computer program product of claim 9, further comprising instructions to:

determine whether an entry is of said first duration by determining whether a value representing a difference between the second value of the entry and the starting point of the query interval is greater than or equal to the duration of the query.

12. The computer program product of claim 4, wherein the search criterion comprises a duration of a query, an ending point of a query interval and a backward search direction, and wherein the instructions to perform the scan comprise instructions to:

traverse a rightmost path from a root node of the tree through one or more nodes to identify an entry that satisfies the search criterion.

13. The computer program product of claim 12, wherein instructions to traverse the rightmost path comprise instructions to:

scan a node by;

identifying the entries in the node of a first duration, and having a first value less than or equal to the ending point of the query interval;

selecting, from among the identified entries in the node, the entry having the largest of the first values; and

if the selected entry includes a pointer to a record in a database table, determining whether the interval of the selected entry satisfies the slot search criterion, and if so, identifying the selected entry as satisfying the search criterion, and

if the selected entry includes a pointer to a child node, traversing a path downwards to the child node, and repeating the scanning at the child node.

14. The computer program product of claim 13, wherein if none of the entries in the node are of said first duration and have a first value less than or equal to the ending point of the query interval, the computer program product further comprises instructions to:

traverse a shortest direct path upwards, from the node towards the root node of the tree, through one or more ancestor nodes to identify the entries in an ancestor node having a second value less than or equal to the ending point of the query interval and having a third value greater than or equal to the duration of the query;

select, from among the identified entries in the ancestor node, the entry having the largest of the second values; and

if the selected entry includes a pointer to a record in a database table, determine whether the interval of the selected entry satisfies the slot search criterion, and if so, identify the selected entry as satisfying the search criterion, and

if the selected entry includes a pointer to a child node, traverse a path downwards to the child node, and repeat the scanning at the child node.

15. The computer program product of claim 13, further comprising instructions to:

determine whether an entry is of said first duration by determining whether a value representing a difference between the ending point of the query interval and the first value of the entry is greater than or equal to the duration of the query.

16. A computer-implemented method to schedule use of resources comprising:

providing a data structure embodied in a computer-readable storage medium, the data structure implementing a tree of nodes having a plurality of inner nodes and a plurality of leaf nodes,

each leaf node including a key having a first value representing a starting point of an interval, a second value representing an ending point of the interval, and a third value representing a duration of the interval, and

each inner node being a root node of a subtree, each inner node including a second key having a first value representing a minimum of the starting points of different intervals in the corresponding subtree, a second value representing a maximum of the ending points of the different intervals in the corresponding subtree, and a third value representing a duration of the longest single interval selected from the different intervals in the corresponding subtree.

17. The method of claim 16, further comprising:

performing a scan of the data structure to identify an entry that satisfies a search criterion.

18. The method of claim 16, wherein each node includes one or more entries, each entry comprising:

a pointer to a record in a database table, the record defining a partial interval, a first value representing a starting point of the particular interval, a second value representing an ending point of the particular interval, and a third value representing a duration of the particular interval;

or

a pointer to a child node, a first value representing a minimum of the starting points of different intervals in a subtree having the child node as a root node of the subtree, a second value representing a maximum of the ending points of the different intervals in the subtree having the child node as the root node of the subtree, and a third value representing a duration of the longest single interval selected from the different intervals in the subtree having the child node as the root node of the subtree.

19. An apparatus to schedule use of resources comprising:

a data structure embodied in a computer-readable storage medium, the data structure implementing a tree of nodes having a plurality of inner nodes and a plurality of leaf nodes,

each leaf node including a key having a first value representing a starting point of an interval, a second value representing an ending point of the interval, and a third value representing a duration of the interval, and

each inner node being a root node of a subtree, each inner node including a second key having a first value representing a minimum of the starting points of different intervals in the corresponding subtree, a second value representing a maximum of the ending points of the different intervals in the corresponding subtree, and a third value representing a duration of the longest single interval selected from the different intervals in the corresponding subtree.

20. The apparatus of claim 19, wherein a scan of the data structure is performed to identify an entry that satisfies a search criterion.