×

Coupled node tree splitting/conjoining method and program

  • US 8,224,861 B2
  • Filed: 05/27/2009
  • Issued: 07/17/2012
  • Est. Priority Date: 11/28/2006
  • Status: Expired due to Fees
First Claim
Patent Images

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.

View all claims
  • 2 Assignments
Timeline View
Assignment View
    ×
    ×