Saving and restoring an interlocking trees datastore

• US 7,340,471 B2
• Filed: 01/16/2004
• Issued: 03/04/2008
• Est. Priority Date: 01/16/2004
• Status: Expired due to Fees

• Current Assignee: Unisys Corporation
• Original Assignee: Unisys Corporation
• Inventors: Claar, Jane Van Keuren, Mazzagatti, Jane Campbell
• Primary Examiner(s): Lee; Wilson
• Assistant Examiner(s): DANG, THANH HA T
• Application Number:
  US10/759,466
• Publication Number:
  US 20050165749A1
• Time in Patent Office: 1,509 Days
• Field of Search: 707/100, 707/3, 707/103.R, 707/104.1
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A tree-based datastore comprising a forest of interconnected trees that can be generated and/or accessed may require specialized saving and restoring processes to ensure that all the links are properly maintained whether it will be restored in full or in part. The processes act on known features of the trees based datastore to generate a file of metadata and packetize each of the nodes of the structure, carefully saving the links and lists of links with old memory addresses accounted for. When restoring the full or partial save to a new memory, a translation table is used to convert the addresses of the nodes and their links to appropriately matched locations in the new memory so that the structure of the data store can be reconstructed in the new location and ensuring that there is sufficient protected memory for the structure as the restore is accomplished.

Claims

1. A method of saving an interlocking trees data store from memory to permanent storage comprising the steps of:

traversing the interlocking trees data store to access each node;

creating a node packet containing all information relevant to the node; and

writing the node packet to permanent storage;

wherein,

the interlocking trees datastore structure comprising elemental root nodes, subcomponent nodes and end-product nodes using asCase and asResult bi-directional links used in determining paths within the interlocking trees datastore structure;

the asCase bi-directional link represents a pointer to a first of two nodes from which a particular node is created; and

the asResult bi-directional link represents a pointer to a second of two nodes from which the particular node is created.

2. The method according to claim 1, wherein said saving of an interlocking trees data store from memory to permanent storage further comprises the step of:

saving supporting structures to permanent storage.

3. The method according to claim 2, wherein the step of saving supporting structures comprises saving any of the following list of structures needed to restore the interlocking trees data store to memory, wherein said list includes:

KStore name, creation date, version or cycle of Save program that created the save file, operating system underlying structure information including at least size of fields used information, sign structure information, elemental root nodes and elemental root node values and pointers to the elemental root nodes'"'"' levels and associated delimiters;

meta data including one or more of the following field types;

user defined types, column descriptions, and permissions;

kState variables including one or more of the following;

switches, data streams, and sign structure information for instance special ordering of asCase bi-directional links in asCase lists;

data sources including one or more of the following;

types, locations, affiliated data streams for learning new knowledge security including one or more of the following;

administrator passwords, user passwords, permissions, saved query locations, and triggers; and

XML-related meta data.

4. The method according to claim 2, wherein saving supporting structures comprises the steps of:

determining informational structures to be saved with the interlocking trees data store; and

,

formatting and writing said informational structures to permanent storage.

5. The method of according to claim 1, wherein creating a node packet containing all information relevant to the node, comprises the steps of:

storing the node'"'"'s current load address in the packet;

storing the asCase and asResult bi-directional links, any other additional fields, an asCase list of pointers and an asResult list of pointers in the packet; and

writing the node packet to permanent storage.

6. The method according to claim 5, wherein prior to storing any packets, memory is allocated for each packet to be stored.

7. The method according to claim 1, wherein traversing the interlocking trees data store to access each node comprises the steps of:

traversing the interlocking trees data store to access each node starting from the primary root, using a typical tree traversal along asCase paths comprising a set of asCase links connecting nodes.

8. The method according to claim 1, wherein traversing the interlocking trees data store to access each node comprises the steps of:

traversing the interlocking trees data store to access each node beginning from an end product nodes.

9. The method according to claim 8, wherein said traversing beginning from end product nodes begins after obtaining access to all end product nodes from a file of end product node information associated with said interlocking trees datastore.

10. The method according to claim 1, wherein traversing the interlocking trees data store to access each node comprises the steps of:

traversing the interlocking trees data store to access each node from a root node.

11. The method according to claim 10, wherein said traversing beginning from said root nodes begins after obtaining access to all root nodes from a file of root node information associated with said interlocking trees datastore.

12. A computer readable storage media containing encoded data comprising a set of instructions executable on a computing system which when executed configure said system to provide the facility to save and restore a trees based datastore, said set of instructions comprising:

a save set having;

a first set to traverse the interlocking trees data store to access each node to be saved;

a second set to create a node packet containing all information relevant to the node to be saved; and

a third set to write the node to be saved as a packet created by the second set to permanent storage connected to said computing system;

wherein,

the interlocking trees datastore structure comprising elemental root nodes, subcomponent nodes and end-product nodes using asCase and asResult bi-directional links used in determining paths within the interlocking trees datastore structure;

the asCase bi-directional link represents a pointer to a first of two nodes from which a particular node is created; and

the asResult bi-directional link represents a pointer to a second of two nodes from which the particular node is created.

13. A computer system having an interlocking trees datastore in a memory of said computer system and having a saving means for saving said interlocking trees datastore for later restoration, said saving means comprising:

means for locating and saving all relevant header information including metadata relevant to restoring said interlocking trees data store,

means for locating each node in said interlocking trees data store and means for saving all data about each located node in a packet form;

wherein,

the interlocking trees datastore comprising elemental root nodes, subcomponent nodes and end-product nodes using asCase and asResult bi-directional links used in determining paths within the interlocking trees datastore structure;

the asCase bi-directional link represents a pointer to a first of two nodes from which a particular node is created; and

the asResult bi-directional link represents a pointer to a second of two nodes from which the particular node is created.

14. The computer system according to claim 13, wherein said means for saving all data determines a saved size for said packet form of said all data about each located node.

15. The computer system according to claim 14, wherein a total size of a saved interlocking trees datastore saved by said saving means is a function of said saved size for each said packet.

16. The computer system according to claim 13, wherein said each packet contains pointer data pointing to addresses of other nodes of said interlocking trees data store that had been linked to the node from which said each packet is constructed in said means for saving.