| 摘要 |
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.
|
