BIT SEQUENCE SEARCH DEVICE, SEARCH METHOD, AND PROGRAM

摘要

Provided is a data structure of a coupled node tree which has released the limit that nodes constituting a pair should be arranged in adjacent storage regions. Provided also are various search methods using the data structure. A branch node includes position information on one (first) and the other (second) of the nodes constituting a pair at a link destination. Index key search is realized by repeating the following process until a leaf node is reached. That is, a process to select the position information on one of the first and the second node in accordance with the bit value of a search key at a discrimination bit contained in the branch node and a process to make a linkage to one of the nodes constituting a pair according to the selected position information.