Indexing hierarchical data

1. 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; and

generate an order tree comprising a hierarchy of entries, where each pointer of the encoding points to a respective one of the entries, and wherein a structure of the order tree encodes an order relation between its hierarchy of entries,

wherein the order tree is a balanced binary tree of entries; and

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

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

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

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

5. 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; and

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

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 1 where each digit of p 1 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 1 corresponds to a position of the first entry;

determination of a number p 2 where each digit of p 2 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 2 corresponds to a position of the second entry; and

comparison of p 1 and p 2 ; and

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

6. 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; and

generate an order tree comprising a hierarchy of entries, where each pointer of the encoding points to a respective one of the entries, and wherein a structure of the order tree encodes an order relation between its hierarchy of entries,

wherein the order tree is a balanced binary tree of entries; and

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

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

9. The medium according to claim 6 , 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.

10. 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; and

generate an order tree comprising a hierarchy of entries, where each pointer of the encoding points to a respective one of the entries, wherein determination of the order relation comprises:

determination of a number p 1 where each digit of p 1 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 1 corresponds to a position of the first entry;

determination of a number p 2 where each digit of p 2 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 2 corresponds to a position of the second entry; and

comparison of p 1 and p 2 ; and

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

11. 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; and

generating an order tree comprising a hierarchy of entries, where each pointer of the encoding points to a respective one of the entries, and wherein a structure of the order tree encodes an order relation between its hierarchy of entries,

wherein the order tree is a balanced binary tree of entries; and

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

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

14. The method according to claim 11 , 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.

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; and

generating an order tree comprising a hierarchy of entries, where each pointer of the encoding points to a respective one of the entries, wherein determining the order relation comprises:

determining a number p 1 where each digit of p 1 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 1 corresponds to a position of the first entry;

determining a number p 2 where each digit of p 2 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 2 corresponds to a position of the second entry; and

comparing p 1 and p 2 ; and

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