Bit string merge sort device, method, and program

A data structure that is a tree structure for a merge key array in a bit string merge sort method that sorts into ascending order or descending order all the keys consisting of bit strings stored in a plurality of sorted key storage areas, wherein in each sorted key storage area all the keys are sorted in ascending order or descending order, by repeating the actions of

• extracting a key that is a minimum value or maximum value from each of the plurality of sorted key storage areas and generating a merge key array, and
• extracting from that merge key array a minimum value or maximum value of keys in that merge key array and storing it in a merged key storage area, and
• extracting a next key, that is a next minimum or next maximum value, from a sorted key storage area wherefrom has been extracted the key that has been stored in the merged key storage area and inserting the next key into the merge key array, and
• extracting from that merge key array a minimum value or maximum value of the keys in that merge key array in which the next key is has been inserted and storing the minimum value or maximum value in the merged key storage area until all the keys are extracted from the plurality of sorted key storage areas and are stored in the merged key storage area, comprising:
• a root node and a node pair, the node pair being a branch node and a leaf node, or a pair of branch nodes, or a pair of leaf nodes located in adjacent storage areas, wherein
• the root node is a node that expresses a starting point of the tree and, which is a leaf node when there is one node in the tree and a branch node when there are two or more nodes,
• the branch node includes a discrimination bit position of a search key with which a bit string search is performed and position information indicating a position of a primary node, which is one node of a node pair of a link target, and the leaf node includes an index key that is a key extracted from a sorted key storage area and is a bit string that is the target of a search, and a process source identifier that identifies the sorted key storage area that had held that key;
• and wherein
• by repeating the linkage successively, at the branch node, to one of the two nodes of a node pair of the link target in accordance with a bit value of a search key of a discrimination bit position included in the branch node, until the leaf node is reached,
• the structure enables the execution of a search with a search key and the identification of a sorted key storage area from which a key obtained as a search result has been extracted.

A bit string merge sort apparatus that sorts into ascending order or descending order all the keys consisting of bit strings stored in a plurality of sorted key storage areas, wherein in each sorted key storage area all the keys are sorted in ascending order or descending order, by repeating the actions of

• extracting a key that is a minimum value or maximum value from each of the plurality of sorted key storage areas and generating a merge key array, and
• extracting from that merge key array a minimum value or maximum value of keys in that merge key array and storing it in a merged key storage area, and
• extracting a next key, that is a next minimum or next maximum value, from a sorted key storage area wherefrom has been extracted the key that has been stored in the merged key storage area and inserting the next key into the merge key array, and
• extracting from that merge key array a minimum value or maximum value of the keys in that merge key array in which the next key is has been inserted and storing the minimum value or maximum value in the merged key storage area until all the keys are extracted from the plurality of sorted key storage areas and are stored in the merged key storage area, comprising:
• a merge tree storage means that holds a key in the merge key array as an index key on a coupled node tree which is used in a bit string search and comprises a root node and a node pair, the node pair being a branch node and a leaf node, or a pair of branch nodes, or a pair of leaf nodes located in adjacent storage areas, wherein
• the root node is a node that expresses a starting point of the tree and, which is a leaf node when there is one node in the tree and a branch node when there are two or more nodes in the tree,
• the branch node includes a discrimination bit position of a search key with which a bit string search is performed and position information indicating a position of a primary node, which is one node of a node pair of a link target, and the leaf node includes a key comprised of bit string that is extracted from one of a plurality of the sorted key storage areas as an index key that is the target of a search and a processing source identifier that identifies the sorted key storage area that held that key, and wherein
• by repeating linkage, at the branch node, to a primary node or a node at a position in a memory area adjacent thereto of a node pair of the link target from an arbitrary node of the tree as a search start node in accordance with a bit value of a search key at a discrimination bit position included in the branch node, until the leaf node is reached, an index key included in the leaf node is made a search result key, which is the search result using the search key of an arbitrary subtree having the search start node as its root node;
• a merge tree generating means that extracts the smallest or largest key from the plurality of sorted key storage areas that hold the sorted keys and generates the coupled node tree and stores the coupled node tree in the merge tree storing means;
• a merging means that performs a minimum or maximum value search on the coupled node tree, obtains either a smallest key that is the minimum value or the largest key that is the maximum value as a search result along with a processing source identifier, and stores the smallest key or largest key in the merged key storage area while deleting the smallest key or largest key from that coupled node tree;
• a next key inserting means that extracts the next key, which is the smallest key that is the minimum value or the largest key that is the maximum value, from the sorted key storage area that is pointed to by the processing source identifier obtained by the merging means and inserts the extracted next key in the coupled node tree;
• and wherein
• by extracting all the keys from the plurality of sorted key storage areas and storing them in the merged key storage area by the merge means and the next key insertion means,
• the keys stored in the plurality of sorted key storage areas are stored in the merged key storage area in ascending order or descending order.