Patent ID: 8250089
Filing Date: 2012-08-21
Classification: G06F

Abstract:
1. A bit string searching apparatus for searching for index keys based on a tree data structure that holds index keys composed of bit strings that are the object of searches by means of a search key composed of a bit string, comprising: a 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 the search key and an area holding a coupled node indicator that is position information indicating the 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 the coupled node indicator; a search start node read-out means obtaining the information indicating a position of a search start node which is an arbitrary node of the coupled node tree and reading out the search start node by means of the information indicating the position of the search start node; a node type determination means 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 means reading out the index key from the area in the leaf node holding the index key; a link means reading out the discrimination bit position and the coupled node indicator from the area in the branch node holding the discrimination bit position and from the area holding the coupled node indicator respectively, and obtaining information indicating the node position of one of the nodes of a node pair by a calculation with the bit value in the search key at the discrimination bit position read out and the coupled node indicator, and, from a storage area indicated by the obtained information indicating the node position, reading out the node stored in the storage area as the link target node; and wherein the node type determination means makes a determination of the node type of the search start node read out by the search start node read-out means, and if the node type indicates a leaf node, the index key read-out means reads out the index key from the leaf node, and if the node type indicates a branch node, the processes of the link means reading out the link target node and the node type determination means determining the node type of the link target node read out are repeated until the node type indicates a leaf node, and the index key read-out means reads out the index key from the leaf node, and an index key stored in the leaf node is obtained as a search result key of an arbitrary subtree of the coupled node tree by means of the search key, the subtree having the search start node as its root node, and the branch nodes on the link path from the search start node to the leaf node are successively saved in a stack.