Coupled node tree splitting/conjoining method and program
First Claim
1. A coupled node tree splitting method, which is executed by a computer, for splitting a coupled node tree being used in a bit string search and having a root node as a 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 secondary node, arranged in adjacent areas of storage,whereinthe nodes have an area that holds a node type, which indicates whether the node is a branch node or a leaf node, andthe branch node having, in addition to the node type, an area that holds a discrimination bit position of a search key with which a bit string search is performed and an area holding position 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, andthe 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 the position information that indicates the position of a primary node of a node pair that is a link target,the method comprising:
- a step of obtaining a split key that establishes an index key that splits a processing source coupled node tree that is to be split;
a processing source minimum value or maximum value obtaining step that determines a minimum value or a maximum value of the index keys of the processing source coupled node tree, by performing sub-steps ofa search-start-node read-out sub-step obtaining position information indicating a position of the root node of the processing source coupled node tree as a searching start node and reading out the searching start node by means of the position information indicating the position of the searching start node,a node type determination sub-step reading out the node type from the area that holds the node type of the node and determining whether the node type indicates a leaf node or a branch node,an index key read-out sub-step reading out the index key from the area in the leaf node holding the index key,a link sub-step reading out the position information indicating the position of a primary node of a node pair that is a link target from the area holding the position information indicating the position of the primary node of a node pair that is a link target, and reading out as a link target node only the primary nodes stored in the area indicated by the position information indicating the primary node of the node pair of the link target that is read out, or reading out as the link target node only the secondary nodes stored in the area the position whereof obtained by a calculation based on the position information indicating the primary node of the node pair of the link target that is read out, andwhereinmaking, by the node type determination sub-step, a determination of the node type of the searching start node read out by the search-start-node read-out sub-step, andif the node type indicates a leaf node,reading out, by the index key read-out sub-step, the index key from the leaf node, andif the node type indicates a branch node, processes of reading outreading out the link target node by the link sub-step and the determination of the node type, by the node type determination sub-step, of the link target node read out are repeated, until the node type indicates a leaf node, andreading out, by the index key read-out sub-step, the index key from the leaf node, andobtaining an index key stored in the leaf node read out in the index key read out sub-step as a search result key, which is a minimum or maximum value of the index keys of the processing source coupled node tree;
a comparing step of comparing the split key with either the minimum value or the maximum value and, if the minimum value is larger than the split key or if the maximum value is smaller than the split key, ending processing;
a generating step of, if the result of the comparison is that the minimum value is not larger than the split key or the maximum value is not smaller than the split key, inserting the minimum value or maximum value index key, so as to generate a new processing target coupled node tree;
a deleting step of deleting the minimum value or maximum value index key from the processing source coupled node tree; and
wherein by making the processing source coupled node tree from which has been deleted the minimum value or maximum value index key into a new processing source coupled node tree,the processing source minimum value or maximum value obtaining step,the comparing step,the generating step,and the deleting stepare repeated until the minimum value or maximum value obtained by the processing source minimum value or maximum value obtaining step becomes larger than or smaller than the split key respectively.
2 Assignments
0 Petitions
Accused Products
Abstract
The minimum value or the maximum value of the index keys of a coupled node tree of a processing source is determined, and the index keys are successively deleted until the index key that is to be the splitting point is reached, the deleted index keys being inserted into the coupled node tree of the processing target, thereby splitting the coupled node tree. Deletion processing is done of one coupled node tree, taking as the processing source in the above-noted splitting method, and insertion processing is done of the other, taken as the processing target, thereby conjoining the coupled node trees.
13 Citations
17 Claims
-
1. A coupled node tree splitting method, which is executed by a computer, for splitting a coupled node tree being used in a bit string search and having a root node as a 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 secondary node, arranged in adjacent areas of storage,
wherein the nodes have an area that holds a 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 with which a bit string search is performed and an area holding position 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, and 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 the position information that indicates the position of a primary node of a node pair that is a link target, the method comprising: -
a step of obtaining a split key that establishes an index key that splits a processing source coupled node tree that is to be split; a processing source minimum value or maximum value obtaining step that determines a minimum value or a maximum value of the index keys of the processing source coupled node tree, by performing sub-steps of a search-start-node read-out sub-step obtaining position information indicating a position of the root node of the processing source coupled node tree as a searching start node and reading out the searching start node by means of the position information indicating the position of the searching start node, a node type determination sub-step reading out the node type from the area that holds the node type of the node and determining whether the node type indicates a leaf node or a branch node, an index key read-out sub-step reading out the index key from the area in the leaf node holding the index key, a link sub-step reading out the position information indicating the position of a primary node of a node pair that is a link target from the area holding the position information indicating the position of the primary node of a node pair that is a link target, and reading out as a link target node only the primary nodes stored in the area indicated by the position information indicating the primary node of the node pair of the link target that is read out, or reading out as the link target node only the secondary nodes stored in the area the position whereof obtained by a calculation based on the position information indicating the primary node of the node pair of the link target that is read out, and wherein making, by the node type determination sub-step, a determination of the node type of the searching start node read out by the search-start-node read-out sub-step, and if the node type indicates a leaf node, reading out, by the index key read-out sub-step, the index key from the leaf node, and if the node type indicates a branch node, processes of reading out reading out the link target node by the link sub-step and the determination of the node type, by the node type determination sub-step, of the link target node read out are repeated, until the node type indicates a leaf node, and reading out, by the index key read-out sub-step, the index key from the leaf node, and obtaining an index key stored in the leaf node read out in the index key read out sub-step as a search result key, which is a minimum or maximum value of the index keys of the processing source coupled node tree; a comparing step of comparing the split key with either the minimum value or the maximum value and, if the minimum value is larger than the split key or if the maximum value is smaller than the split key, ending processing; a generating step of, if the result of the comparison is that the minimum value is not larger than the split key or the maximum value is not smaller than the split key, inserting the minimum value or maximum value index key, so as to generate a new processing target coupled node tree; a deleting step of deleting the minimum value or maximum value index key from the processing source coupled node tree; and wherein by making the processing source coupled node tree from which has been deleted the minimum value or maximum value index key into a new processing source coupled node tree, the processing source minimum value or maximum value obtaining step, the comparing step, the generating step, and the deleting step are repeated until the minimum value or maximum value obtained by the processing source minimum value or maximum value obtaining step becomes larger than or smaller than the split key respectively. - View Dependent Claims (2, 3, 4, 5)
-
-
6. A coupled node tree conjoining method, which is executed by a computer, for conjoining two coupled node trees each of which is used in a bit string search and having a root node as a starting point of the tree and node pairs which are configurational elements of the tree and which are two nodes, a primary node and secondary node, arranged in adjacent areas of storage,
wherein the nodes have an area that holds a 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 with which a bit string search is performed 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, and 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, the method comprising: -
a processing source minimum value or maximum value obtaining step that determines a minimum value or a maximum value of the index keys of a processing source coupled node tree, that is, one of two coupled node trees, by performing sub-steps of a search-start-node read-out sub-step obtaining information indicating a position of the root node of the processing source coupled node tree as a searching start node and reading out the searching start node by means of the information indicating the position of the searching start node, a node type determination sub-step reading out the node type from the area that holds the node type of the node and determining whether the node type indicates a leaf node or a branch node, an index key read-out sub-step reading out the index key from the area in the leaf node holding the index key, a link sub-step reading out the information indicating the position of a primary node of a node pair that is a link target from the area in the branch node holding the information indicating the position of the primary node of a node pair that is a link target, and reading out as a link target node only the primary nodes stored in the area indicated by the position information indicating the primary node of the node pair of the link target that is read out, or reading out as the link target node only the secondary nodes stored in the area the position whereof obtained by a calculation based on the position information indicating the primary node of the node pair of the link target that is read out, and wherein making, by the node type determination sub-step, a determination of the node type of the searching start node read out by the search-start-node read-out sub-step, and if the node type indicates a leaf node, reading out, by the index key read-out sub-step, the index key from the leaf node, and if the node type indicates a branch node, processes of reading out the link target node by the link sub-step and the determination of the node type, by the node type determination sub-step, of the link target node read out are repeated, until the node type indicates a leaf node, and reading out, by the index key read-out sub-step, the index key from the leaf node, and obtaining an index key stored in the leaf node read out in the index key read out sub-step as a search result key, which is the minimum or maximum value of the index keys of the processing source coupled node tree; an inserting step that inserts the minimum value or the maximum value into a processing target coupled node tree, that is, the other coupled node tree of the two coupled node trees; a deleting step that deletes the minimum value or the maximum value from the processing source coupled node tree; and
whereinby making the processing source coupled node tree from which has been deleted the minimum value or maximum value index key into a new processing source coupled node tree, the processing source minimum value or maximum value obtaining step, the inserting step, and the deleting step are repeated until the processing source coupled node tree is completely deleted. - View Dependent Claims (7, 8, 9)
-
-
10. A coupled node tree splitting method, which is executed by a computer, for splitting a coupled node tree being used in a bit string search and having a root node as a starting point of the tree and node pairs which are configurational elements of the tree and which are two nodes, a primary node and secondary node, arranged in adjacent areas of storage,
wherein the nodes have an area that holds a 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 with which a bit string search is performed and an area holding position 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, and 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 the position information that indicates the position of a primary node of a node pair that is a link target, the method comprising: -
a step of obtaining a split key that establishes an index key that splits a processing source coupled node tree that is to be split; a search step that obtains the split key as a search result key using the split key as a search key and the root node of the processing source coupled node tree as a search start node, through performing sub-steps of a search-start-node read-out sub-step obtaining position information indicating a position of the root node of the processing source coupled node tree as a searching start node and reading out the searching start node by means of the position information indicating the position of the searching start node, a node type determination sub-step reading out the node type from the area that holds the node type of the node and determining whether the node type indicates a leaf node or a branch node, an index key read-out sub-step reading out the index key from the area in the leaf node holding the index key, a link sub-step reading out the discrimination bit position and the information indicating the position of one node of a node pair that is a link target from the area in the branch node holding the discrimination bit position and from the area holding the information indicating the position of one node of a node pair that is a link target respectively, and obtaining information indicating a node position by a calculation with a bit value in the search key for the discrimination bit position read out and the information indicating the position of one node of a node pair that is a link target, and reading out a node at the node position indicated by the obtained information as a link target node, and wherein the node type determination sub-step makes a determination of the node type of the root node read out by the root node read-out sub-step, and if the node type indicates a leaf node, the index key read-out sub-step reads out the index key from the leaf node, and if the node type indicates a branch node, reading out the link target node by the link sub-step and the determination of the node type, by the node type determination sub-step, of the link target node read out are repeated, until the node type indicates a leaf node, and the index key read-out sub-step reads out the index key from the leaf node as the search result key while position information for the area in which the search start node is positioned and the position information for the areas in which the link target nodes from the link start node to the leaf node are all successively stored in a stack; a split node obtaining step that reads out the position information from the stack until the position information of the primary node or secondary node is obtained, then obtains, as a split node, the primary node or secondary node whose position information has been read out; a generating step that generates a new processing target coupled node tree by inserting a split node tree that is a subtree having the split node as the root node; and a deleting step that deletes the split node tree from the processing source coupled node tree. - View Dependent Claims (11, 12, 13)
-
-
14. A coupled node tree conjoining method, which is executed by a computer, for conjoining two coupled node trees each of which is used in a bit string search and having a root node as a 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 secondary node, arranged in adjacent areas of storage,
wherein the nodes have an area that holds a 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 with which a bit string search is performed 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, and 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, the method comprising: -
a processing source maximum value or minimum value obtaining step that determines a maximum value or a minimum value of the index keys of a processing source coupled node tree, that is, one of two coupled node trees, by performing sub-steps of a search-start-node read-out sub-step obtaining information indicating a position of the root node of the processing source coupled node tree as a searching start node and reading out the searching start node by means of the information indicating the position of the searching start node, a node type determination sub-step reading out the node type from the area that holds the node type of the node and determining whether the node type indicates a leaf node or a branch node, an index key read-out sub-step reading out the index key from the area in the leaf node holding the index key, a link sub-step reading out the information indicating the position of a primary node of a node pair that is a link target from the area in the branch node holding the information indicating the position of the primary node of a node pair that is a link target, and reading out as a link target node only the secondary nodes stored in the area the position whereof obtained by a calculation based on the position information indicating the primary node of the node pair of the link target that is read out, or reading out as the link target node only the primary nodes stored in the area indicated by the position information indicating the primary node of the node pair of the link target that is read out, and wherein making, by the node type determination sub-step, a determination of the node type of the searching start node read out by the search-start-node read-out sub-step, and if the node type indicates a leaf node, reading out, by the index key read-out sub-step, the index key from the leaf node, and if the node type indicates a branch node, processes of reading out the link target node by the link sub-step and the determination of the node type, by the node type determination sub-step, of the link target node read out are repeated, until the node type indicates a leaf node, and reading out, by the index key read-out sub-step, the index key from the leaf node, and obtaining an index key stored in the leaf node read out in the index key read out sub-step as a search result key, which is the maximum or minimum value of the index keys of the processing source coupled node tree; a processing target minimum value or maximum value obtaining step that determines a minimum value or a maximum value of the index keys of a processing target coupled node tree, that is, another of two coupled node trees, by performing sub-steps of a search-start-node read-out sub-step obtaining information indicating a position of the root node of the processing source coupled node tree as a searching start node and reading out the searching start node by means of the information indicating the position of the searching start node, a node type determination sub-step reading out the node type from the area that holds the node type of the node and determining whether the node type indicates a leaf node or a branch node, an index key read-out sub-step reading out the index key from the area in the leaf node holding the index key, a link sub-step reading out the information indicating the position of a primary node of a node pair that is a link target from the area in the branch node holding the information indicating the position of the primary node of a node pair that is a link target, and reading out as a link target node only the primary nodes stored in the area indicated by the position information indicating the primary node of the node pair of the link target that is read out, or reading out as the link target node only the secondary nodes stored in the area the position whereof obtained by a calculation based on the position information indicating the primary node of the node pair of the link target that is read out, and wherein making, by the node type determination sub-step, a determination of the node type of the searching start node read out by the search-start-node read-out sub-step, and if the node type indicates a leaf node, reading out, by the index key read-out sub-step, the index key from the leaf node, and if the node type indicates a branch node, processes of reading out the link target node by the link sub-step and the determination of the node type, by the node type determination sub-step, of the link target node read out are repeated, until the node type indicates a leaf node, and reading out, by the index key read-out sub-step, the index key from the leaf node, and obtaining an index key stored in the leaf node read out in the index key read out sub-step as a search result key, which is the minimum or maximum value of the index keys of the processing source coupled node tree; a difference bit position obtaining step that determines a difference bit position between the maximum value of the index keys of the processing source coupled node tree determined by the processing source maximum value or minimum value obtaining step and the minimum value of the index keys of the processing target coupled node tree determined by the processing target minimum value or maximum value obtaining step or between the minimum value of the index keys of the processing source coupled node tree determined by the processing source maximum value or minimum value obtaining step and the maximum value of the index keys of the processing target coupled node tree determined by the processing target minimum value or maximum value obtaining step; a split/conjoin node obtaining step that determines a split/conjoin node, which is the root node of a subtree that is to be split from the processing source coupled node tree and conjoined to the processing target coupled node tree, based on the difference bit position obtained by the difference bit position obtaining step; a conjoining position obtaining step that determines a processing target conjoining position for conjoining the split/conjoin node determined by the split/conjoin node obtaining step, based on the difference bit position determined by the difference bit position obtaining step; an inserting step that inserts the split/conjoin node determined by the split/conjoin node obtaining step at the processing target conjoining position determined by the conjoining position obtaining step; a deleting step that deletes the split/conjoin node determined by the split/conjoin node obtaining step from the processing source coupled node tree; and wherein by making the processing source coupled node tree from which has been deleted the split/conjoin node into a new processing source coupled node tree, the processing source maximum value or minimum value obtaining step, the processing target minimum value or maximum value obtaining step, the difference bit position obtaining step, the split/conjoin node obtaining step, the conjoining position obtaining step, the inserting step, and the deleting step are repeated until the processing source coupled node tree is completely deleted. - View Dependent Claims (15, 16, 17)
-
Specification