Indexing hierarchical data

• US 9,280,575 B2
• Filed: 07/19/2013
• Issued: 03/08/2016
• Est. Priority Date: 07/20/2012
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP SE
• Inventors: Finis, Jan, Brunel, Robert
• Primary Examiner(s): Ly, Anh
• Application Number:
  US13/946,081
• Publication Number:
  US 20140025708A1
• Time in Patent Office: 963 Days
• Field of Search: 707/797, 707/E17.044, 707/778, 707/786, 707/758, 707/756, 707/704, 707/791, 707/752, 707/736, 707/656, 707/634, 707/693, 707/695, 707/829, 707/956, 707/802, 707/809, 707/801, 707/813, 707/E17.124, 711/164, 711/124, 711/161, 711/162, 711/163, 711/167, 711/113, 711/100, 711/120, 711/121, 711/122, 711/123, 709/217, 709/218, 709/219, 709/246, 709/203, 370/254, 370/255, 370/256, 719/312, 712/239, 714/45, 714/38.1, 714/38.2, 714/38.3, 714/38.4
• US Class Current: 1/1
• CPC Class Codes: G06F 16/185 Hierarchical storage management [HSM] systems, e.g. file migration or policies thereof details of archiving G06F16/11
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/9027 Trees

Abstract

A system includes generation of an encoding for each of a hierarchy of nodes, each of the nodes associated with one or more attributes, and the encoding for each node including a first pointer and a second pointer, and generation of an order tree comprising a hierarchy of entries, where each pointer of the encoding points to a respective one of the entries, wherein the encoding and the order tree indicate a position of each node in the hierarchy of nodes.

Claims

1. A computing system comprising:

one or more memory storing processor-executable program code; and

one or more processor to execute the processor-executable program code in order to cause the computing system to;

generate an encoding for each of a hierarchy of nodes, each of the nodes associated with one or more attributes, and the encoding for each node including a first pointer and a second pointer;

generate an order tree comprising a hierarchy of entries that is different from the hierarchy of nodes and the encoding, wherein each pointer of the encoding points to a respective one of the entries, and wherein the encoding and the order tree indicate a position of each node in the hierarchy of nodes; and

use the order tree to support queries on the hierarchy of the nodes;

wherein the processor is to execute the processor-executable program code in order to cause the computing system to;

determine an order relation between a first entry of the order tree and a second entry of the order tree based on a structure of the order tree; and

wherein determination of the order relation comprises;

determination of a number p₁ where each digit of p₁ corresponds to a position of each entry on a first path from the first entry to a root entry of the order tree, and a least significant digit of p₁ corresponds to a position of the first entry;

determination of a number p₂ where each digit of p₂ corresponds to a position of each entry on a second path from the second entry to the root entry of the order tree, and a least significant digit of p₂ corresponds to a position of the second entry; and

comparison of p₁ and p₂.

2. A computing system according to claim 1, wherein the order tree is a balanced binary tree of entries.

3. A computing system according to claim 2, wherein the encoding comprises an interval encoding, and

wherein, for each node, the first pointer indicates a lower interval bound of the node and the second pointer indicates an upper interval bound of the node.

4. A computing system according to claim 1, wherein the encoding comprises an interval encoding, and

wherein, for each node, the first pointer indicates a lower interval bound of the node and the second pointer indicates an upper interval bound of the node.

5. A non-transitory computer-readable medium storing program code, the program code executable by one or more processor of a computing system to cause the computing system to:

generate an encoding for each of a hierarchy of nodes, each of the nodes associated with one or more attributes, and the encoding for each node including a first pointer and a second pointer;

generate an order tree comprising a hierarchy of entries that is different from the hierarchy of nodes and the encoding, wherein each pointer of the encoding points to a respective one of the entries, and wherein the encoding and the order tree indicate a position of each node in the hierarchy of nodes; and

use the order tree to support queries on the hierarchy of the nodes;

the program code further executable by a processor of a computing system to cause the computing system to;

determine an order relation between a first entry of the order tree and a second entry of the order tree based on a structure of the order tree; and

wherein determination of the order relation comprises;

determination of a number p₁ where each digit of p₁ corresponds to a position of each entry on a first path from the first entry to a root entry of the order tree, and a least significant digit of p₁ corresponds to a position of the first entry;

determination of a number p₂ where each digit of p₂ corresponds to a position of each entry on a second path from the second entry to the root entry of the order tree, and a least significant digit of p₂ corresponds to a position of the second entry; and

comparison of p₁ and p₂.

6. A medium according to claim 5, wherein the order tree is a balanced binary tree of entries.

7. A medium according to claim 6, wherein the encoding comprises an interval encoding, and

wherein, for each node, the first pointer indicates a lower interval bound of the node and the second pointer indicates an upper interval bound of the node.

8. A medium according to claim 5, wherein the encoding comprises an interval encoding, and

wherein, for each node, the first pointer indicates a lower interval bound of the node and the second pointer indicates an upper interval bound of the node.

9. A computer-implemented method comprising:

generating an encoding for each of a hierarchy of nodes, each of the nodes associated with one or more attributes, and the encoding for each node including a first pointer and a second pointer;

generating an order tree comprising a hierarchy of entries that is different from the hierarchy of nodes and the encoding, wherein each pointer of the encoding points to a respective one of the entries, and wherein the encoding and the order tree indicate a position of each node in the hierarchy of nodes; and

using the order tree to support queries on the hierarchy of the nodes;

the method further comprising;

determining an order relation between a first entry of the order tree and a second entry of the order tree based on a structure of the order tree; and

wherein determining the order relation comprises;

determining a number p₁ where each digit of p₁ corresponds to a position of each entry on a first path from the first entry to a root entry of the order tree, and a least significant digit of p₁ corresponds to a position of the first entry;

determining a number p₂ where each digit of p₂ corresponds to a position of each entry on a second path from the second entry to the root entry of the order tree, and a least significant digit of p₂ corresponds to a position of the second entry; and

comparing p₁ and p₂.

10. A method according to claim 9, wherein the order tree is a balanced binary tree of entries.

11. A method according to claim 10, wherein the encoding comprises an interval encoding, and

wherein, for each node, the first pointer indicates a lower interval bound of the node and the second pointer indicates an upper interval bound of the node.

12. A method according to claim 11, wherein the encoding comprises an interval encoding, and

wherein, for each node, the first pointer indicates a lower interval bound of the node and the second pointer indicates an upper interval bound of the node.

13. A computing system comprising:

a memory storing processor-executable program code; and

a processor to execute the processor-executable program code in order to cause the computing system to;

generate an encoding for each of a hierarchy of nodes, each of the nodes associated with one or more attributes, and the encoding for each node including a first pointer and a second pointer;

generate an order tree comprising a hierarchy of entries, where each pointer of the encoding points to a respective one of the entries, wherein the encoding and the order tree indicate a position of each node in the hierarchy of nodes; and

determine an order relation between a first entry of the order tree and a second entry of the order tree based on a structure of the order tree;

wherein determination of the order relation comprises;

determination of a number p₁ where each digit of p₁ corresponds to a position of each entry on a first path from the first entry to a root entry of the order tree, and a least significant digit of p₁ corresponds to a position of the first entry;

determination of a number p₂ where each digit of p₂ corresponds to a position of each entry on a second path from the second entry to the root entry of the order tree, and a least significant digit of p₂ corresponds to a position of the second entry; and

comparison of p₁ and p₂.

14. A non-transitory computer-readable medium storing program code, the program code executable by a processor of a computing system to cause the computing system to:

generate an encoding for each of a hierarchy of nodes, each of the nodes associated with one or more attributes, and the encoding for each node including a first pointer and a second pointer;

generate an order tree comprising a hierarchy of entries, where each pointer of the encoding points to a respective one of the entries,

wherein the encoding and the order tree indicate a position of each node in the hierarchy of nodes; and

determine an order relation between a first entry of the order tree and a second entry of the order tree based on a structure of the order tree;

wherein determination of the order relation comprises;

determination of a number p₁ where each digit of p₁ corresponds to a position of each entry on a first path from the first entry to a root entry of the order tree, and a least significant digit of p₁ corresponds to a position of the first entry;

determination of a number p₂ where each digit of p₂ corresponds to a position of each entry on a second path from the second entry to the root entry of the order tree, and a least significant digit of p₂ corresponds to a position of the second entry; and

comparison of p₁ and p₂.

15. A computer-implemented method comprising:

generating an encoding for each of a hierarchy of nodes, each of the nodes associated with one or more attributes, and the encoding for each node including a first pointer and a second pointer;

generating an order tree comprising a hierarchy of entries, where each pointer of the encoding points to a respective one of the entries,

wherein the encoding and the order tree indicate a position of each node in the hierarchy of nodes; and

determining an order relation between a first entry of the order tree and a second entry of the order tree based on a structure of the order tree;

wherein determining the order relation comprises;

determining a number p₁ where each digit of p₁ corresponds to a position of each entry on a first path from the first entry to a root entry of the order tree, and a least significant digit of p₁ corresponds to a position of the first entry;

determining a number p₂ where each digit of p₂ corresponds to a position of each entry on a second path from the second entry to the root entry of the order tree, and a least significant digit of p₂ corresponds to a position of the second entry; and

comparing p₁ and p₂.