Indexing stored data

• US 20060004715A1
• Filed: 06/30/2004
• Published: 01/05/2006
• 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.
• Granted Patent: US 7,761,474 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 an information carrier, the computer program product being operable to cause 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 an interval, and a third value representing a duration of an interval, and

each inner node being a root node of a subtree, each inner node including 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.

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 an interval, a first value representing a starting point of the interval, a second value representing an ending point of the interval, and a third value representing a duration of the interval;

or

a pointer to a child node, a first value representing a minimum of the starting points of intervals in a subtree having the child node as its root node, a second value representing a maximum of the ending points of the intervals in the subtree having the child node as its root node, and a third value representing a maximum duration of the intervals in the subtree having the child node as its root node.

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 an 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 sufficient 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 include 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 sufficient 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 sufficient 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 sufficient 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 sufficient 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 sufficient 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 comprising:

providing 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 an interval, and a third value representing a duration of an interval, and

each inner node being a root node of a subtree, each inner node including 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.

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 an interval, a first value representing a starting point of the interval, a second value representing an ending point of the interval, and a third value representing a duration of the interval;

or

a pointer to a child node, a first value representing a minimum of the starting points of intervals in a subtree having the child node as its root node, a second value representing a maximum of the ending points of the intervals in the subtree having the child node as its root node, and a third value representing a maximum duration of the intervals in the subtree having the child node as its root node.

19. An apparatus comprising:

means for providing 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 an interval, and a third value representing a duration of an interval, and

each inner node being a root node of a subtree, each inner node including 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.

20. The apparatus of claim 19, further comprising:

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