Bit string searching apparatus using a coupled node tree with a root node and a node pair stored in adjacent areas that is formed by a branch node and a leaf node, branch nodes, or leaf nodes; the branch node including a discrimination bit position in the search key and information indicating a position of a primary node that is one node of a node pair; the leaf node including an index key formed by a bit string; from the root node of an arbitrary subtree of the coupled node tree, linking is repeated based on the search key's bit value at the discrimination bit position and information indicating a position of a primary node until a leaf node is reached; an index key stored in the leaf node is obtained as a search result key of the subtree by means of the search key.