Patent ID: 8386526
Filing Date: 2013-02-26
Classification: G06F

Abstract:
1. A coupled node tree backup apparatus which backs up an arbitrary subtree of a coupled node tree being used in a bit string search comprising: the coupled node tree having a root node as the starting point of the tree and node pairs which are configurational elements of the tree and which are two nodes, a primary node and a non-primary node, arranged in adjacent areas of storage, wherein the nodes have an area that holds the node type which indicates whether the node is a branch node or a leaf node, and the branch node having, in addition to the node type, an area that holds a discrimination bit position of a search key and an area holding information that indicates a position of a primary node of a node pair that is a link target but not having an area holding an index key composed of a bit string that is an object of searches, the leaf node having, in addition to the node type, an area holding the index key composed of a bit string that is the object of searches but not having an area that holds a discrimination bit position of the search key nor an area holding information that indicates the position of a primary node of a node pair that is a link target, and wherein at the branch node with an arbitrary node of the tree as a search start node, in response to a bit value of an index key at the discrimination bit position included in the branch node, by repeated linking to a primary node of a node pair of the link target or a node at a position in a memory area adjacent thereto until the leaf node is reached, an index key stored in the storage area pointed at by the second kind of position information included in the leaf node is made a search result key, which is a search result using a search key of an arbitrary subtree having the search start node as its root node; a traverse start node specifying means specifying the root node of the subtree to be backed up as a traverse start node that is the starting point of the sequence in which the nodes are to be backed up; a first node backup means making a traverse from the traverse start node specified by the traverse start node specifying means through linking to only the primary nodes or only the non-primary nodes until a leaf node is reached, and while successively storing in a stack the position information pointing to the position of each of those nodes on the path from the traverse start node until the leaf node, successively storing the contents of those nodes in a separate storage area from the storage area in which the coupled node tree is located; a next traverse start node specifying means reading out the position information from the stack until the position information of the primary node or non-primary node is obtained, then specifying, as a next traverse start node, a non-primary node or primary node that is paired with the primary node or non-primary node whose storage information has been read out; a second node backup means making a traverse from the next traverse start node specified by the next traverse start node specifying means through linking to only the primary nodes or only the non-primary nodes until a leaf node is reached, and while successively storing in the stack the position information pointing to the position of each of those nodes on the path from the traverse start node until the leaf node, successively storing the contents of those nodes in the separate storage area; and wherein the backup of the nodes by the second node backup means and the next traverse start node specification by the next traverse start node specifying means are repeated.