×

Storing hierarchical data to enable paging

  • US 8,209,353 B2
  • Filed: 03/31/2009
  • Issued: 06/26/2012
  • Est. Priority Date: 03/31/2009
  • Status: Active Grant
First Claim
Patent Images

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 all claims
  • 1 Assignment
Timeline View
Assignment View
    ×
    ×