Path-caching mechanism to improve performance of path-related operations in a repository
First Claim
1. A computer-implemented method of processing path-based operations, the method comprising:
- storing, in a particular cache entry in a path cache, a separation value that indicates a quantity of nodes that separate a particular node from a root node in a hierarchy of nodes;
wherein the particular cache entry in the path cache includes a pathname that specifies a complete path from the root node to the particular node in the hierarchy of nodes;
determining that at least one cache entry is to be evicted from the path cache based on the path cache being full and a new cache entry needing to be inserted;
in response to the determination that at least one cache entry is to be evicted from the path cache, selecting the particular cache entry for eviction from the path cache based at least in part on the separation value;
wherein cache entries with higher separation values are selected for eviction before cache entries with lower separation values;
evicting the selected particular cache entry from the path cache;
wherein the method is performed by one or more computing devices.
0 Assignments
0 Petitions
Accused Products
Abstract
A method and apparatus for processing path-based database operations is provided. According to one aspect, a path cache is maintained. For each hierarchical node that is traversed during a path-determining operation, it is determined whether a cache entry corresponding to that node is already contained in the path cache. If such a cache entry is already contained in the path cache, then the path indicated in that cache entry is used to complete the pathname for the node for which the operation is being performed. As a result, hierarchically higher nodes do not need to be traversed to complete the operation. Alternatively, if such a cache entry is not already contained in the path cache, then a cache entry for the node currently being traversed is generated and inserted into the path cache for use in subsequent path-determining operations.
317 Citations
20 Claims
-
1. A computer-implemented method of processing path-based operations, the method comprising:
-
storing, in a particular cache entry in a path cache, a separation value that indicates a quantity of nodes that separate a particular node from a root node in a hierarchy of nodes; wherein the particular cache entry in the path cache includes a pathname that specifies a complete path from the root node to the particular node in the hierarchy of nodes; determining that at least one cache entry is to be evicted from the path cache based on the path cache being full and a new cache entry needing to be inserted; in response to the determination that at least one cache entry is to be evicted from the path cache, selecting the particular cache entry for eviction from the path cache based at least in part on the separation value; wherein cache entries with higher separation values are selected for eviction before cache entries with lower separation values; evicting the selected particular cache entry from the path cache; wherein the method is performed by one or more computing devices. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
7. A non-transitory computer-readable medium storing instructions which, when executed by one or more processors, cause:
-
storing, in a particular cache entry in a path cache, a separation value that indicates a quantity of nodes that separate a particular node from a root node in a hierarchy of nodes; wherein the particular cache entry in the path cache includes a pathname that specifies a complete path from the root node to the particular node in the hierarchy of nodes; determining that at least one cache entry is to be evicted from the path cache based on the path cache being full and a new cache entry needing to be inserted; in response to the determination that at least one cache entry is to be evicted from the path cache, selecting the particular cache entry for eviction from the path cache based at least in part on the separation value; wherein cache entries with higher separation values are selected for eviction before cache entries with lower separation values; evicting the selected particular cache entry from the path cache. - View Dependent Claims (8, 9, 10, 11, 12)
-
-
13. A method comprising:
-
storing, in a particular cache entry in a path cache, a descendant value that indicates a quantity of other nodes that descend from a particular node in a hierarchy of nodes; wherein the particular cache entry in the path cache includes a pathname that specifies a complete path from a root node to the particular node in the hierarchy of nodes; determining that at least one cache entry is to be evicted from the path cache based on the path cache being full and a new cache entry needing to be inserted; in response to the determination that at least one cache entry is to be evicted from the path cache, selecting the particular cache entry for eviction from the path cache based at least in part on the descendant value; evicting the selected particular cache entry from the path cache; wherein the method is performed by one or more computing devices. - View Dependent Claims (14, 15, 16)
-
-
17. A non-transitory computer-readable medium storing instructions which, when executed by one or more processors, cause:
-
storing, in a particular cache entry in a path cache, a descendant value that indicates a quantity of other nodes that descend from a particular node in a hierarchy of nodes; wherein the particular cache entry in the path cache includes a pathname that specifies a complete path from a root node to the particular node in the hierarchy of nodes; and determining that at least one cache entry is to be evicted from the path cache based on the path cache being full and a new cache entry needing to be inserted; in response to the determination that at least one cache entry is to be evicted from the path cache, selecting the particular cache entry for eviction from the path cache based at least in part on the descendant value; evicting the selected particular cache entry from the path cache. - View Dependent Claims (18, 19, 20)
-
Specification