Saving and restoring an interlocking trees datastore

• US 20050165749A1
• Filed: 01/16/2004
• Published: 07/28/2005
• Est. Priority Date: 01/16/2004
• Status: Active Grant

• Current Assignee: Unisys Corporation
• Original Assignee: Unisys Corporation
• Inventors: Claar, Jane Van Keuren, Mazzagatti, Jane Campbell
• Granted Patent: US 7,340,471 B2
• Time in Patent Office: Days
• 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.

2. The method of 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 of 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/cycle of Save program that created the save file,

OS underlying structure information including at least size of fields used information,

sign structure information if not saved below,

elemental root nodes or 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,

sign structure information for instance special ordering for 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, if any.

4. A method of saving an interlocking trees data store from memory to permanent storage according to claim 2, wherein saving supporting structures comprises the steps of:

determining which informational structures will be saved with the interlocking trees data store, And,

formatting and writing said informational structures to permanent storage

5. A method of saving an interlocking trees data store from memory to permanent storage according to claim 1, wherein creating a node packet containing all information relevant to the node, comprises the steps of:

storing the ndde'"'"'s current load address in the packet

storing the Case and Result pointers, any other additional fields, the asCase list of pointers and the asResult list of pointers in the packet

writing the node packet to permanent storage.

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

7. A method of saving an interlocking trees data store from memory to permanent storage 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 the asCase paths

8. A method of saving an interlocking trees data store from memory to permanent storage 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 endproduct nodes.

9. The method of 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. A method of saving an interlocking trees data store from memory to permanent storage 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 root nodes.

11. The method of 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 method of restoring an interlocking trees data store from permanent storage to memory comprising the steps of:

Allocating memory and reading supporting structures required before the interlocking trees data store is restored, from permanent storage into memory

reading each node packet and allocating memory for nodes—

creating a translation table of old memory addresses &

new memory addresses for each node

reading each node packet and reconstructing nodes and pointer lists

Allocating memory and reading supporting structures that require address translation using the translation table to be restored, from permanent storage into memory.

13. The method of claim 12 wherein said allocating memory and reading support structures step finds elemental root node packets and data from said elemental root nodes on a first pass, and then the remaining steps of claim 12 are executed.

14. A set of instructions executable on a computing system which when executed configure said system to provide the facility to save 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,

a second set to create a node packet containing all information relevant to the node, and

a third set to write the node created by the second set to permanent storage connected to said computing system.

15. A set of instructions, executable on a computing system which when executed configure said system to provide the facility to restore a trees based datastore, said set of instructions comprising:

a restore set, having;

instructions to reconstruct metadata, and

an address translation table maintenance and using set for establishing an address translation table to convert addresses between addresses in saved packets and addresses in a restored interlocking trees datastore.

16. The set of instructions set forth in claim 15 further comprising:

a save set having;

a first set to traverse the interlocking trees data store to access each node,

a second set to create a node packet containing all information relevant to the node, and,

a third set to write the node created by the second set to permanent storage connected to said computing system.

17. A computer system for running an interlocking trees datastore program so that an interlocking trees data store can function in a main memory of said computer system, said computer system having a program for saving said interlocking trees datastore and a program for restoring said interlocking trees datastore wherein addresses of said interlocking trees datastore and said restored interlocking trees datastore are not the same, said program for restoring said interlocking trees datastore having means to establish an address translation table to translate addresses found in node packets created by said save program to new addresses in said restored interlocking trees datastore.

18. 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.

19. The computer system of claim 18 wherein said means for saving discovers a saved size for said packet form of said all data about each located node.

20. The computer system of claim 19 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.

21. The computer system of claim 18 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.