Techniques related to binary encoding of hierarchical data objects to support efficient path navigation of the hierarchical data objects

1. A method comprising:

for a hierarchical data object comprising field names that are each associated with one or more field values in said hierarchical data object, generating a plurality of hash codes, each hash code of said plurality of hash codes corresponding to a respective field name of said field names;

generating a hash-code mapping that maps each hash code of said plurality of hash codes to a respective field-name identifier of a plurality of field-name identifiers;

generating a field-name mapping that maps each field name of said field names to a respective field-name identifier of said plurality of field-name identifiers;

generating a hierarchical tree of nodes, wherein said hierarchical tree of nodes comprises non-leaf nodes and leaf nodes, wherein a particular non-leaf node of said non-leaf nodes comprises:

a child node mapping that maps said particular non-leaf node to one or more child nodes of said particular non-leaf node; and

a field-name-identifier-to-child mapping that maps a respective field-name identifier of said plurality of field-name identifiers to each of said one or more child nodes of said particular non-leaf node;

storing, in a record representing said hierarchical data object, said hash-code mapping, said field-name mapping, and for said particular non-leaf node of said non-leaf nodes, the child node mapping and the field-name-identifier-to-child mapping; and

wherein said method is performed by one or more computing devices.

2. The method of claim 1 , wherein generating said hash-code mapping comprises:

sorting said plurality of hash codes prior to storing said plurality of hash codes in said hash-code mapping.

3. The method of claim 1 , wherein, for each field-name identifier of said plurality of field-name identifiers, said field-name mapping references a respective memory location in a field-name collection, said field-name collection contiguously storing said field names and lengths of said field names within a memory address space.

4. The method of claim 3 , wherein generating said hash-code mapping comprises: resolving duplicate hash codes based on said field-name collection.

5. The method of claim 1 , wherein each leaf node of said leaf nodes references a respective memory location of a corresponding field value in a field-value collection, said field-value collection contiguously storing said field values within a memory address space.

6. The method of claim 5 , wherein said hash-code mapping, said field-name mapping, and said field-value collection are shared by a plurality of hierarchical data objects.

7. One or more non-transitory storage media storing instructions which, when processed by one or more computing devices, cause:

for a hierarchical data object comprising field names that are each associated with one or more field values in said hierarchical data object, generating a plurality of hash codes, each hash code of said plurality of hash codes corresponding to a respective field name of said field names;

generating a hash-code mapping that maps each hash code of said plurality of hash codes to a respective field-name identifier of a plurality of field-name identifiers;

generating a field-name mapping that maps each field name of said field names to a respective field-name identifier of said plurality of field-name identifiers;

generating a hierarchical tree of nodes, wherein said hierarchical tree of nodes comprises non-leaf nodes and leaf nodes, wherein a particular non-leaf node of said non-leaf nodes comprises:

a child node mapping that maps said particular non-leaf node to one or more child nodes of said particular non-leaf node; and

a field-name-identifier-to-child mapping that maps a respective field-name identifier of said plurality of field-name identifiers to each of said one or more child nodes of said particular non-leaf node; and

storing, in a record representing said hierarchical data object, said hash-code mapping, said field-name mapping, and for said particular non-leaf node of said non-leaf nodes, the child node mapping and the field-name-identifier-to-child mapping.

8. The one or more non-transitory storage media of claim 7 , wherein generating said hash-code mapping comprises:

sorting said plurality of hash codes prior to storing said plurality of hash codes in said hash-code mapping.

9. The one or more non-transitory storage media of claim 7 , wherein, for each field-name identifier of said plurality of field-name identifiers, said field-name mapping references a respective memory location in a field-name collection, said field-name collection contiguously storing said field names and lengths of said field names within a memory address space.

10. The one or more non-transitory storage media of claim 9 , wherein generating said hash-code mapping comprises:

resolving duplicate hash codes based on said field-name collection.

11. The one or more non-transitory storage media of claim 7 , wherein each leaf node of said leaf nodes references a respective memory location of a corresponding field value in a field-value collection, said field-value collection contiguously storing said field values within a memory address space.

12. The one or more non-transitory storage media of claim 11 , wherein said hash-code mapping, said field-name mapping, and said field-value collection are shared by a plurality of hierarchical data objects.

13. A method comprising:

for a hierarchical data object comprising field names that are associated with field values in said hierarchical data object, storing a representation of said hierarchical data object, wherein said representation of said hierarchical data object comprises a hash-code mapping and a hierarchical tree of nodes, wherein said hash-code mapping maps each field hash code of a plurality of field hash codes to a respective field-name identifier of a plurality of field-name identifiers, wherein said hierarchical tree of nodes comprises non-leaf nodes and leaf nodes, wherein said field values correspond to said leaf nodes, wherein a particular non-leaf node of said non-leaf nodes comprises:

a child node mapping that maps said particular non-leaf node to one or more child nodes of said particular non-leaf node; and

a field-name-identifier-to-child mapping that maps a respective field-name identifier of said plurality of field-name identifiers to each of said one or more child nodes of said particular non-leaf node;

to resolve a path expression comprising a plurality of path steps:

generating a sequence of step-hash codes, each step-hash code of said sequence corresponding to a path step of said plurality of path steps;

based on said hash-code mapping, translating said sequence of step-hash codes into a sequence of step-field-name identifiers;

navigating said hierarchical tree of nodes based on said sequence of step-field-name identifiers;

wherein said method is performed by one or more computing devices.

14. The method of claim 13 , wherein navigating said hierarchical tree of nodes based on said sequence of step-field-name identifiers comprises:

for each step-field-name identifier of said sequence of step-field-name identifiers, determining one or more corresponding non-leaf nodes based on said field-name-identifier-to-child mapping.

15. The method of claim 13 , wherein navigating said hierarchical tree of nodes based on said sequence of step-field-name identifiers comprises:

finding a particular step-field-name identifier in said field-name-identifier-to-child mapping based on performing a binary search on said field-name-identifier-to-child mapping.

16. The method of claim 13 , wherein based on said hash-code mapping, translating said sequence of step-hash codes into said sequence of step-field-name identifiers comprises:

finding a particular step-field-name identifier in said hash-code mapping based on performing a binary search on said hash-code mapping.

17. The method of claim 13 , wherein generating said sequence of step-hash codes comprises:

using a same set of step-hash codes for each hierarchical data object of a plurality of hierarchical data objects to resolve said path express over said plurality of hierarchical data objects.

18. The method of claim 13 , wherein a similar hierarchical data object shares a field-name mapping of the hierarchical data object in such a manner that avoids computing, by the one or more computing devices, one or more step-hash codes for the similar hierarchical data object, the field-name mapping storing a relationship between each field name of said field names and a respective field-name identifier of said plurality of field-name identifiers.

19. One or more non-transitory storage media storing instructions which, when processed by one or more computing devices, cause:

for a hierarchical data object comprising field names that are associated with field values in said hierarchical data object, storing a representation of said hierarchical data object, wherein said representation of said hierarchical data object comprises a hash-code mapping and a hierarchical tree of nodes, wherein said hash-code mapping maps each field hash code of a plurality of field hash codes to a respective field-name identifier of a plurality of field-name identifiers, wherein said hierarchical tree of nodes comprises non-leaf nodes and leaf nodes, wherein said field values correspond to said leaf nodes, wherein a particular non-leaf node of said non-leaf nodes comprises:

a child node mapping that maps said particular non-leaf node to one or more child nodes of said particular non-leaf node; and

a field-name-identifier-to-child mapping that maps a respective field-name identifier of said plurality of field-name identifiers to each of said one or more child nodes of said particular non-leaf node;

to resolve a path expression comprising a plurality of path steps:

generating a sequence of step-hash codes, each step-hash code of said sequence corresponding to a path step of said plurality of path steps;

based on said hash-code mapping, translating said sequence of step-hash codes into a sequence of step-field-name identifiers;

navigating said hierarchical tree of nodes based on said sequence of step-field-name identifiers.

20. The one or more non-transitory storage media of claim 19 , wherein navigating said hierarchical tree of nodes based on said sequence of step-field-name identifiers comprises:

for each step-field-name identifier of said sequence of step-field-name identifiers, determining one or more corresponding non-leaf nodes based on said field-name-identifier-to-child mapping.

21. The one or more non-transitory storage media of claim 19 , wherein navigating said hierarchical tree of nodes based on said sequence of step-field-name identifiers comprises:

finding a particular step-field-name identifier in said field-name-identifier-to-child mapping based on performing a binary search on said field-name-identifier-to-child mapping.

22. The one or more non-transitory storage media of claim 19 , wherein based on said hash-code mapping, translating said sequence of step-hash codes into said sequence of step-field-name identifiers comprises:

finding a particular step-field-name identifier in said hash-code mapping based on performing a binary search on said hash-code mapping.

23. The one or more non-transitory storage media of claim 19 , wherein generating said sequence of step-hash codes comprises:

using a same set of step-hash codes for each hierarchical data object of a plurality of hierarchical data objects to resolve said path expression over said plurality of hierarchical data objects.

24. The one or more non-transitory storage media of claim 19 , wherein the instructions include instructions, that when executed by said one or more computing devices, cause a similar hierarchical data object to share a field-name mapping of the hierarchical data object in such a manner that avoids computing, by the one or more computing devices, one or more step-hash codes for the similar hierarchical data object, the field-name mapping storing a relationship between each field name of said field names and a respective field-name identifier of said plurality of field-name identifiers.