INDEXING HIERARCHICAL DATA

• US 20160140154A1
• Filed: 01/27/2016
• Published: 05/19/2016
• Est. Priority Date: 07/20/2012
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP SE
• Inventors: Finis, Jan, Brunel, Robert
• Granted Patent: US 9,576,011 B2
• Time in Patent Office: Days
• 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.

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 computing system according to claim 1, 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.

6. A computing system according to claim 5, 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 pi 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₂.

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

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

9. A medium according to claim 8, 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.

10. A medium according to claim 7, 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.

11. A medium according to claim 7, 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.

12. A medium according to claim 11, wherein determination of the order relation comprises:

determination of a number pi 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 pi 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₂.

13. 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.

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

15. A method according to claim 14, 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.

16. A method according to claim 13, 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.

17. A method according to claim 13, 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.

18. A medium according to claim 17, wherein determining the order relation comprises:

determining a number pi where each digit of pi 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₂.