Systems and methods for navigating through a hierarchy of nodes stored in a database

• US 10,817,510 B1
• Filed: 09/08/2014
• Issued: 10/27/2020
• Est. Priority Date: 05/04/2014
• Status: Active Grant

• Current Assignee: Veritas Technologies, LLC (Whitehouse Group Ltd.)
• Original Assignee: Veritas Technologies, LLC (Whitehouse Group Ltd.)
• Inventors: Haynes, Tim
• Primary Examiner(s): Leroux, Etienne P
• Assistant Examiner(s): Agharahimi, Farhad
• Application Number:
  US14/480,558
• Time in Patent Office: 2,241 Days
• Field of Search: None
• CPC Class Codes: G06F 16/211 Schema design and management
• CPC Class Codes: G06F 16/2358 Change logging, detection, and notification replication G06F16/27
• CPC Class Codes: G06F 16/2393 Updating materialised views
• CPC Class Codes: G06F 16/2453 Query optimisation

Abstract

The disclosed computer-implemented method for navigating through a hierarchy of nodes stored in a database may include (1) receiving a request to access a database that stores a set of nodes organized in a hierarchy, wherein the hierarchy is divided into contiguous subsections and each subsection is stored in a separate page and (2) in response to the request, traversing a path through the hierarchy of nodes by (a) identifying an initial node in the path and looking up an initial page that contains the initial node, (b) loading the page from the database into local memory, the page including the initial node in the path and one or more subsequent nodes in the path, and (c) navigating to the one or more subsequent nodes in the path by accessing the page loaded into local memory instead of accessing the database. Additional methods, systems, and computer-readable media are also disclosed.

Claims

1. A computer-implemented method for navigating through a hierarchy of nodes stored in a database, at least a portion of the method being performed by a computing device comprising at least one processor, the method comprising:

dividing a set of nodes organized in a hierarchy into contiguous subsections by;

selecting a number of nodes to allocate to each subsection based at least in part on an amount of time involved in loading the number of nodes into local memory from a database;

storing each subsection in a separate page within the database, wherein each node in the hierarchy represents at least one of;

a child node descended from a parent node, a parent node with at least one child node, or a root node that represents a highest parent node on a path within a page, and each node within the hierarchy is uniquely identified by a primary key; and

storing within each node at least one association between the node and each related parent node, child node, or root node by storing within the node the primary key of each related node;

receiving a request to access nodes within the database;

in response to the request, traversing a path through the hierarchy of nodes by;

identifying an initial node in the path and looking up an initial page that contains the initial node and one or more subsequent nodes in the path;

loading the initial page from the database into local memory such that each node contained in the initial page is accessible via local memory;

compressing contents of the initial page by serializing each node within the initial page into a single field within a page table;

navigating to the one or more subsequent nodes in the path by accessing the nodes loaded into local memory instead of accessing the database; and

storing a page key of a subsequent page within at least one of a root node within the initial page or a lowest node on the path within the initial page.

2. The method of claim 1, wherein the path comprises nodes distributed across multiple servers.

3. The method of claim 1, wherein selecting the number of nodes to allocate to each subsection is based further on at least one of:

a total number of nodes within the hierarchy of nodes; and

a frequency with which nodes within the hierarchy of nodes are modified.

4. The method of claim 1, wherein:

each page that stores a subsection of nodes is uniquely identified by a separate page key.

5. The method of claim 4, further comprising:

while traversing the path through the hierarchy of nodes, determining that the one or more subsequent nodes in the path is stored on the subsequent page; and

navigating to the one or more subsequent nodes by loading the subsequent page into local memory.

6. The method of claim 5, wherein:

each parent node that has a child node on a separate page stores the page key of the page that stores the child node;

traversing the path through the hierarchy of nodes comprises traversing a path down the hierarchy of nodes; and

loading the subsequent page into local memory comprises identifying, within the lowest node on the path within the initial page, the page key of the subsequent page.

7. The method of claim 5, wherein:

traversing the path through the hierarchy of nodes comprises traversing a path up the hierarchy of nodes; and

loading the subsequent page into local memory comprises;

identifying the primary key of the one or more subsequent nodes within the root node of the page that, for each page, stores the primary key of the parent node of the root node of the page; and

using the primary key of the one or more subsequent nodes to look up the page key of the subsequent page.

8. The method of claim 5, wherein storing the page key of the subsequent page within the initial page further comprises:

traversing the path through the hierarchy of nodes comprises traversing a path up the hierarchy of nodes; and

loading the subsequent page into local memory comprises directly identifying the page key of the subsequent page within the initial page.

9. The method of claim 5, further comprising, after loading the subsequent page into local memory, caching both the initial page and the subsequent page in local memory.

10. The method of claim 1, wherein loading the initial page from the database into local memory comprises loading the initial page and preloading at least one additional page that potentially stores nodes within the path into local memory.

11. The method of claim 1, further comprising:

adding additional nodes to the initial page until a number of nodes within the initial page reaches a predetermined threshold; and

in response to the number of nodes reaching the predetermined threshold, separating the initial page into two pages that each contain a contiguous subsection of nodes.

12. A system for navigating through a hierarchy of nodes stored in a database, the system comprising at least one processor, wherein the processor is configured to:

divide a set of nodes organized in a hierarchy into contiguous subsections by;

selecting a number of nodes to allocate to each subsection based at least in part on an amount of time involved in loading the number of nodes into local memory from a database;

storing each subsection in a separate page within the database, wherein each node in the hierarchy represents at least one of;

a child node descended from a parent node, a parent node with at least one child node, or a root node that represents a highest parent node within a path within a page, and each node within the hierarchy is uniquely identified by a primary key; and

storing within each node at least one association between the node and each related parent node, child node, or root node by storing within the node the primary key of each related node;

receive a request to access nodes within the database;

in response to the request, traverse a path through the hierarchy of nodes by;

identifying an initial node in the path and looking up an initial page that contains the initial node and one or more subsequent nodes in the path;

loading the initial page from the database into local memory such that each node contained in the initial page is accessible via local memory;

compressing contents of the initial page by serializing each node within the initial page into a single field within a page table;

navigating to the one or more subsequent nodes in the path by accessing the nodes loaded into local memory instead of accessing the database; and

store a page key of a subsequent page within at least one of a root node within the initial page or a lowest node on the path within the initial page.

13. The system of claim 12, wherein the path comprises nodes distributed across multiple servers.

14. The system of claim 12, wherein selecting the number of nodes to allocate to each subsection is based further on at least one of:

a total number of nodes within the hierarchy of nodes; and

a frequency with which nodes within the hierarchy of nodes are modified.

15. The system of claim 12, wherein:

each page that stores a subsection of nodes is uniquely identified by a separate page key.

16. The system of claim 15, wherein the processor is further configured to:

while traversing the path through the hierarchy of nodes, determine that the one or more subsequent nodes in the path is stored on the subsequent page; and

navigate to the one or more subsequent nodes by loading the subsequent page into local memory.

17. The system of claim 16, wherein:

each parent node that has a child node on a separate page stores the page key of the page that stores the child node;

traversing the path through the hierarchy of nodes comprises traversing a path down the hierarchy of nodes; and

loading the subsequent page into local memory comprises identifying, within the lowest node on the path within the initial page, the page key of the subsequent page.

18. The system of claim 16, wherein:

traversing the path through the hierarchy of nodes comprises traversing a path up the hierarchy of nodes; and

loading the subsequent page into local memory comprises;

identifying the primary key of the one or more subsequent nodes within the root node of the page that, for each page, stores the primary key of the parent node of the root node of the page; and

using the primary key of the one or more subsequent nodes to look up the page key of the subsequent page.

19. The method of claim 16, wherein storing the page key of the subsequent page within the initial page further comprises:

traversing the path through the hierarchy of nodes comprises traversing a path up the hierarchy of nodes; and

loading the subsequent page into local memory comprises directly identifying the page key of the subsequent page within the initial page.

20. A non-transitory computer-readable medium comprising one or more computer-executable instructions that, when executed by at least one processor of a computing device, cause the computing device to:

divide a set of nodes organized in a hierarchy into contiguous subsections by;

selecting a number of nodes to allocate to each subsection based at least in part on an amount of time involved in loading the number of nodes into local memory from a database;

storing each subsection in a separate page within the database, wherein each node in the hierarchy represents at least one of;

a child node descended from a parent node, a parent node with at least one child node, or a root node that represents a highest parent node on a path within a page, and each node within the hierarchy is uniquely identified by a primary key; and

storing within each node at least one association between the node and each related parent node, child node, or root node by storing within the node the primary key of each related node;

receive a request to access nodes within the database;

in response to the request, traverse a path through the hierarchy of nodes by;

identifying an initial node in the path and looking up an initial page that contains the initial node and one or more subsequent nodes in the path;

loading the initial page from the database into local memory such that each node contained in the initial page is accessible via local memory;

compressing contents of the initial page by serializing each node within the initial page into a single field within a page table;

navigating to the one or more subsequent nodes in the path by accessing the nodes loaded into local memory instead of accessing the database; and

store a page key of a subsequent page within at least one of a root node within the initial page or a lowest node on the path within the initial page.