Indexing stored data

US7761474B2 · kind B2 · utility

Assignee

• SAP AG · DE

Inventors

• Hendrik Lock · Linkenheim-Hochstetten, DE
• Daniel Booss · Angelbachtal, DE

Key dates

• Filing date: Jun 30, 2004
• Grant date: Jul 20, 2010
• Expiry date: Jan 4, 2028

Classification

• Technology area (CPC Y): Emerging Cross-Sectional Technologies
• CPC primary: Y10S707/956
• WIPO field: Computer technology
• WIPO sector: Electrical engineering

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.