Storing hierarchical data to enable paging
First Claim
1. A machine-implemented method for performing operations, the method comprising:
- storing, in a non-transitory machine-readable medium, for each node of a plurality of nodes of a tree, a preorder number identifying a position of said each node in a depth-first search ordering of said plurality of nodes that starts at a root node of said tree and explores an unexplored child before backtracking;
storing, in said non-transitory machine-readable medium, for said each node a count of all the nodes of a subtree rooted at said each node, said subtree comprising said each node; and
in response to receiving a request to perform an edit operation to delete an existing node from said plurality of nodes or to add a new node to said plurality of nodes of said tree, at least one processor changing the preorder number stored for at least one node in said plurality of nodes of said tree and changing the count stored for at least another node in said plurality of nodes of said tree;
wherein said edit operation is comprised in a plurality of edit operations, said plurality of edit operations comprise one or more add operations and one or more delete operations;
performing said plurality of edit operations, by said at least one processor determining said each node should not have said preorder number changed because the number of said one or more add operations that have been performed or will be performed on a subset of nodes in said plurality of nodes is equal to the number of said one or more delete operations that have been performed or will be performed on said subset of nodes, wherein the preorder number of said each node is greater than another preorder number of another node in said subset of nodes; and
performing another operation that identifies a particular page number of a page to be displayed among a plurality of pages, wherein said another operation comprises identifying which nodes of said plurality of nodes have the preorder number of a value ranging from p*(n−
1)+1 to p*(n−
1)+p, wherein n represents said particular page number, and wherein p represents a page size.
1 Assignment
0 Petitions
Accused Products
Abstract
A method and apparatus for performing a paging operation on a tree having a plurality of nodes is provided. A preorder number and a subtree size are maintained in a machine-readable medium for each of the plurality of nodes of the tree. The preorder number associated with a particular node of the tree identifies a position for the particular node in a depth-first search ordering of the plurality of nodes of the tree. The subtree size associated with a particular node of the tree identifies a count of all the nodes in a subtree rooted at the particular node. In response to receiving a request to perform a paging operation on the plurality of nodes of the tree, a set of nodes that satisfy the paging operation may be determined using the preorder number and the subtree size associated with each node of the tree.
17 Citations
20 Claims
-
1. A machine-implemented method for performing operations, the method comprising:
-
storing, in a non-transitory machine-readable medium, for each node of a plurality of nodes of a tree, a preorder number identifying a position of said each node in a depth-first search ordering of said plurality of nodes that starts at a root node of said tree and explores an unexplored child before backtracking; storing, in said non-transitory machine-readable medium, for said each node a count of all the nodes of a subtree rooted at said each node, said subtree comprising said each node; and in response to receiving a request to perform an edit operation to delete an existing node from said plurality of nodes or to add a new node to said plurality of nodes of said tree, at least one processor changing the preorder number stored for at least one node in said plurality of nodes of said tree and changing the count stored for at least another node in said plurality of nodes of said tree; wherein said edit operation is comprised in a plurality of edit operations, said plurality of edit operations comprise one or more add operations and one or more delete operations; performing said plurality of edit operations, by said at least one processor determining said each node should not have said preorder number changed because the number of said one or more add operations that have been performed or will be performed on a subset of nodes in said plurality of nodes is equal to the number of said one or more delete operations that have been performed or will be performed on said subset of nodes, wherein the preorder number of said each node is greater than another preorder number of another node in said subset of nodes; and performing another operation that identifies a particular page number of a page to be displayed among a plurality of pages, wherein said another operation comprises identifying which nodes of said plurality of nodes have the preorder number of a value ranging from p*(n−
1)+1 to p*(n−
1)+p, wherein n represents said particular page number, and wherein p represents a page size. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
10. One or more non-transitory machine-readable media comprising one or more sequences of instructions for performing operations, which when executed by at least one processor, cause said at least one processor to perform:
-
storing, for each node of a plurality of nodes of a tree, a preorder number identifying a position of said each node in a depth-first search ordering of said plurality of nodes that starts at a root node of said tree and explores an unexplored child before backtracking; storing, in said non-transitory machine-readable medium, for said each node a count of all the nodes of a subtree rooted at said each node, said subtree comprising said each node; and in response to receiving a request to perform an edit operation to delete an existing node from said plurality of nodes or to add a new node to said plurality of nodes of said tree, changing the preorder number stored for at least one node in said plurality of nodes of said tree and changing the count stored for at least another node in said plurality of nodes of said tree; wherein said edit operation is comprised in a plurality of edit operations, said plurality of edit operations comprise one or more add operations and one or more delete operations; performing said plurality of edit operations, by said at least one processor determining said each node should not have said preorder number changed because the number of said one or more add operations that have been performed or will be performed on a subset of nodes in said plurality of nodes is equal to the number of said one or more delete operations that have been performed or will be performed on said subset of nodes, wherein the preorder number of said each node is greater than another preorder number of another node in said subset of nodes; and performing another operation that identifies a particular page number of a page to be displayed among a plurality of pages, wherein said another operation comprises identifying which nodes of said plurality of nodes have the preorder number of a value ranging from p*(n−
1)+1 to p*(n−
1)+p, wherein n represents said particular page number, and wherein p represents a page size. - View Dependent Claims (11, 12, 13, 14, 15, 16, 17, 18)
-
-
19. A system for performing operations, the system comprising at least one processor and a non-transitory machine-readable media storing instructions to be executed by the at least one processor, the system comprising:
-
means for storing, in said non-transitory machine-readable medium, for each node of a plurality of nodes of a tree, a preorder number identifying a position of said each node in a depth-first search ordering of said plurality of nodes that starts at a root node of said tree and explores an unexplored child before backtracking; means for storing, in said non-transitory machine-readable medium, for said each node a count of all the nodes of a subtree rooted at said each node, said subtree comprising said each node; and means, responsive to receipt of a request to perform an edit operation to delete an existing node from said plurality of nodes or to add a new node to said plurality of nodes of said tree, for changing the preorder number stored for at least one node in said plurality of nodes of said tree and changing the count stored for at least another node in said plurality of nodes of said tree; wherein said edit operation is comprised in a plurality of edit operations, said plurality of edit operations comprise one or more add operations and one or more delete operations; means for performing said plurality of edit operations, by said at least one processor determining said each node should not have said preorder number changed because the number of said one or more add operations that have been performed or will be performed on a subset of nodes in said plurality of nodes is equal to the number of said one or more delete operations that have been performed or will be performed on said subset of nodes, wherein the preorder number of said each node is greater than another preorder number of another node in said subset of nodes; and means for performing another operation that identifies a particular page number of a page to be displayed among a plurality of pages, wherein said another operation comprises identifying which nodes of said plurality of nodes have the preorder number of a value ranging from p*(n−
1)+1 to p*(n−
1)+p, wherein n represents said particular page number, and wherein p represents a page size. - View Dependent Claims (20)
-
Specification