Changing nodes for conjoined tree data structure
A system, method, and device for managing updates to a hypercube is provided. The method includes (i) obtaining a tree data structure to represent the data, (ii) receiving a request to change the N-conjoined tree data structure, (iii) enforcing a rule that requires each leaf node to have an associated linkage to each tree in the N-conjoined tree data structure while changing the N-conjoined tree data structure in accordance with the request, and (iv) providing an updated N-conjoined tree data structure. The tree data structure is an N-conjoined tree data structure, and N is a positive integer.
1. A system, comprising:
one or more processors configured to:
obtain a tree data structure to represent data comprised in a dataset, wherein the tree data structure is an N-conjoined tree data structure, and N is a positive integer;
receive a request to change the N-conjoined tree data structure;
enforce a first rule that requires each leaf node to have an associated linkage to each tree in the N-conjoined tree data structure while changing the N-conjoined tree data structure in accordance with the request; and
enforce a second rule that requires that each leaf node has at most a single associated child node for each tree;
provide an updated N-conjoined tree data structure; and
a memory coupled to the one or more processors and configured to provide the one or more processors with instructions.
2. The system of claim 1 , wherein the request to change the N-conjoined tree data structure comprises a request to add a new branch or leaf node.
3. The system of claim 2 , wherein:
changing the N-conjoined tree data in accordance with the request to add the new branch comprises adding a new branch node to a particular tree of N-trees in the N-conjoined tree data structure; and
the new branch node is added as a child of a root node for the particular tree or another branch in a higher branch-level in a hierarchy of the particular tree.
4. The system of claim 3 , wherein the N-conjoined tree data structure is updated to comprise metadata associated with the new branch node, the metadata comprising an indication of a relationship between the new branch node and one or more of (i) the root node for the particular tree, (ii) another branch in a higher branch-level in the hierarchy of the particular tree, and (iii) an adjacent branch node in the particular tree.
5. The system of claim 2 , wherein changing the N-conjoined tree data structure in accordance with a request to add a new leaf comprises:
adding a new leaf node to a particular tree of N-trees in the N-conjoined tree data structure; and
storing a linkage between the new leaf node and each tree in the N-conjoined tree data structure.
6. The system of claim 5 , wherein a linkage between the new leaf node and a particular tree in the N-conjoined tree data structure comprises an indication of one or more of a parent node and a child node in the particular tree.
7. The system of claim 1 , wherein the one or more processors are further configured to enforce a second rule that requires that each leaf node has a single associated parent node for each tree.
8. The system of claim 1 , wherein the request to change the N-conjoined tree data structure comprises a request to insert a new branch or leaf node.
9. The system of claim 8 , wherein:
changing the N-conjoined tree data structure in accordance with the request to insert the new branch comprises inserting a new branch node in a particular tree of N-trees in the N-conjoined tree data structure; and
the new branch node is added as a child of a root node for the particular tree or another branch in a higher branch-level in a hierarchy of the particular tree.
10. The system of claim 9 , wherein the N-conjoined tree data structure is updated to comprise metadata associated with the new branch node, the metadata comprising an indication of a relationship between the new branch node and one or more of (i) the root node for the particular tree, (ii) the other branch in a higher branch-level in a hierarchy of the particular tree, and (iii) an adjacent branch node in the particular tree.
11. The system of claim 8 , wherein:
changing the N-conjoined tree data in accordance with the request to insert a new leaf node comprises inserting the new leaf node to the N-conjoined tree data structure;
storing a linkage between the new leaf node and each tree in the N-conjoined tree data structure; and
updating linkages of existing leaf nodes to a corresponding parent node and/or child node based on an insertion of the new leaf node.
12. The system of claim 11 , wherein the new leaf node is inserted at a beginning or middle of child nodes for at least a particular tree in the N-conjoined tree data structure.
13. The system of claim 11 , wherein the one or more processors are further configured to enforce a second rule that requires that each leaf node has at most a single associated child node for each tree with respect to the new leaf node or an existing leaf node for which a child-parent relationship has changed based on the insertion of the new leaf node.
14. The system of claim 1 , wherein the request to change the N-conjoined tree data structure comprises a request to delete a branch or leaf node.
15. The system of claim 14 , wherein the changing the N-conjoined tree data structure in accordance with the request to delete a particular branch node comprises:
deleting the particular branch node for a particular tree of N-trees in the N-conjoined tree data structure; and
deleting all child nodes of the particular branch node in the particular tree, wherein the deletion is applied to the child nodes with respect to all N-trees in the N-conjoined tree data structure.
16. The system of claim 15 , wherein the changing the N-conjoined tree data structure in accordance with the request to delete a particular branch node further comprises:
updating metadata indicating linkages between a plurality of nodes in the N-trees to reflect an updated linkage based on deletion of the particular branch.
17. The system of claim 14 , wherein the changing the N-conjoined tree data structure in accordance with the request to delete a particular leaf node comprises:
deleting the particular leaf node in the N-conjoined tree data structure; and
updating metadata indicating linkages between a plurality of nodes in the N-trees to reflect an updated child-parent linkage based on deletion of the particular leaf node.
18. A method, comprising:
obtaining a tree data structure to represent data comprised in a dataset, wherein the tree data structure is an N-conjoined tree data structure, and N is a positive integer;
receiving a request to change the N-conjoined tree data structure;
enforcing a first rule that requires each leaf node to have an associated linkage to each tree in the N-conjoined tree data structure while changing the N-conjoined tree data structure in accordance with the request;
enforcing a second rule that requires that each leaf node has at most a single associated child node for each tree; and
providing an updated N-conjoined tree data structure.
19. A computer program product embodied in a non-transitory computer readable medium and comprising computer instructions for:
obtaining a tree data structure to represent data comprised in a dataset, wherein the tree data structure is an N-conjoined tree data structure, and N is a positive integer;
receiving a request to change the N-conjoined tree data structure;
enforcing a first rule that requires each leaf node to have an associated linkage to each tree in the N-conjoined tree data structure while changing the N-conjoined tree data structure in accordance with the request;
enforcing a second rule that requires that each leaf node has at most a single associated child node for each tree; and
providing an updated N-conjoined tree data structure.