Storing Hierarchical Data to Enable Paging

• US 20100250611A1
• Filed: 03/31/2009
• Published: 09/30/2010
• Est. Priority Date: 03/31/2009
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Krishnamurthy, Sanjay
• Granted Patent: US 8,209,353 B2
• Time in Patent Office: Days
• US Class Current: 707/797
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: G06F 16/904 Browsing; Visualisation therefor for navigating the web G06F16/954; browsing optimisation for the web G06F16/957
• CPC Class Codes: G06F 40/14 Tree-structured documents parsing G06F40/205; validation G06F40/226

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.

Claims

1. A machine-implemented method for performing a paging operation on a tree having a plurality of nodes, comprising:

maintaining, in a machine-readable medium, for each node of said plurality of nodes of said tree, a preorder number and a subtree size, wherein the preorder number associated with a particular node of said tree identifies a position for said particular node in a depth-first search ordering of said plurality of nodes of said tree, and wherein the subtree size associated with said particular node identifies a count of all the nodes of a subtree rooted at said particular node; and

in response to receiving a request to perform said paging operation on said plurality of nodes of said tree, determining a set of nodes that satisfy said paging operation using the preorder number and the subtree size of at least one node of said plurality of nodes of said tree.

2. The machine-implemented method of claim 1, wherein said maintaining comprises:

upon performing an add operation that adds a child node to a parent node of said tree, incrementing the subtree size associated with said parent node.

3. The machine-implemented method of claim 1, wherein said maintaining comprises:

upon performing an add operation that adds a child node to a parent node of said tree, updating the preorder number associated with said child node to a number equal to the sum of the preorder number associated with said parent node and the subtree size of said parent node.

4. The method of claim 1, wherein said maintaining comprises:

upon performing a delete operation that removes a child node from a parent node of said tree, decrementing the subtree size associated with said parent node.

5. The method of claim 1, wherein said maintaining comprises:

upon performing a delete operation that removes a child node from a parent node of said tree, decrementing all preorder numbers, associated with nodes of said tree, that are greater than the preorder number associated with the child node being removed in the delete operation.

6. The method of claim 1, wherein said maintaining comprises:

arranging a plurality of edit operations in a sequence, wherein each said plurality of edit operations is to be performed on one of said plurality of nodes of said tree, and wherein said sequence orders said plurality of edit operations based on the preorder number of the node on which each of said plurality of edit operations is to be performed; and

performing said plurality of edit operations in order of said sequence.

7. The method of claim 6, wherein said performing comprises:

updating, in a single update operation, the preorder number of said particular node to reflect the performance of two or more of said plurality of edit operations.

8. The method of claim 6, wherein said particular node has a particular preorder number, wherein said plurality of edit operations comprise one or more add operations and one or more delete operations, and wherein said performing comprises:

determining said particular node should not have said particular 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, and wherein the preorder number of each of said subset of nodes is less than said particular preorder number.

9. The method of claim 1, wherein said paging operation identifies a particular page number, wherein said set of nodes are associated with said particular page number, wherein determining said set of nodes comprises:

identifying which nodes of said plurality of nodes have a preorder number that has 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.

10. The method of claim 1, wherein said plurality of nodes are to be displayed in association with a plurality of pages, and wherein determining said set of nodes comprises:

determining a total number of pages upon which said plurality of nodes should be displayed by dividing the subtree size of a root node of said tree by the number of said plurality of nodes of said tree to be displayed on each of said plurality of pages.

11. A machine-readable medium storing one or more sequences of instructions for performing a paging operation on a tree having a plurality of nodes, which when executed, perform:

maintaining, in a machine-readable medium, for each node of said plurality of nodes, a preorder number and a subtree size, wherein said preorder number identifies, for a particular node of said tree, a position for said particular node in a depth-first search ordering of said plurality of nodes of said tree, and wherein said subtree size identifies, for said particular node of said tree, a count of all the nodes of a subtree rooted at said particular node; and

in response to receiving a request to perform said paging operation on said plurality of nodes of said tree, determining a set of nodes that satisfy said paging operation using the preorder number and the subtree size of at least one node of said plurality of nodes of said tree.

12. The machine-readable medium of claim 11, wherein said maintaining comprises:

upon performing an add operation that adds a child node to a parent node of said tree, incrementing the subtree size associated with said parent node.

13. The machine-readable medium of claim 11, wherein said maintaining comprises:

upon performing an add operation that adds a child node to a parent node of said tree, updating the preorder number associated with said child node to a number equal to the sum of the preorder number associated with said parent node and the subtree size of said parent node.

14. The machine-readable medium of claim 11, wherein said maintaining comprises:

upon performing a delete operation that removes a child node from a parent node of said tree, decrementing the subtree size associated with said parent node.

15. The machine-readable medium of claim 11, wherein said maintaining comprises:

upon performing a delete operation that removes a child node from a parent node of said tree, decrementing all preorder numbers, associated with nodes of said tree, that are greater than the preorder number associated with the child node being removed in the delete operation.

16. The machine-readable medium of claim 11, wherein said maintaining comprises:

arranging a plurality of edit operations in a sequence, wherein each said plurality of edit operations is to be performed on one of said plurality of nodes of said tree, and wherein said sequence orders said plurality of edit operations based on the preorder number of the node on which each of said plurality of edit operations is to be performed; and

performing said plurality of edit operations in order of said sequence.

17. The machine-readable medium of claim 16, wherein said performing comprises:

updating, in a single update operation, the preorder number of said particular node to reflect the performance of two or more of said plurality of edit operations.

18. The machine-readable medium of claim 16, wherein said particular node has a particular preorder number, wherein said plurality of edit operations comprise one or more add operations and one or more delete operations, and wherein said performing comprises:

determining said particular node should not have said particular 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, and wherein the preorder number of each of said subset of nodes is less than said particular preorder number.

19. The machine-readable medium of claim 11, wherein said paging operation identifies a particular page number, wherein said set of nodes are associated with said particular page number, wherein determining said set of nodes comprises:

identifying which nodes of said plurality of nodes have a preorder number that has 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.

20. The machine-readable medium of claim 11, wherein said plurality of nodes are to be displayed in association with a plurality of pages, and wherein determining said set of nodes comprises:

determining a total number of pages upon which said plurality of nodes should be displayed by dividing the subtree size of a root node of said tree by the number of said plurality of nodes of said tree to be displayed on each of said plurality of pages.