PURPOSE: To efficiently retrieve a record by preparing an index in which record numbers of all the records corresponding to a key are stored in a tree structure in the order of value, in the case that plural records corresponding to the key exist.

CONSTITUTION: There are two kinds in a leaf node on a tree structure index. One is the case that one record corresponds to one key, and in the leaf node in this case, a key and a record number are stored in a pair. For instance, it is a leaf node LN1 related to a writer's name, Mayumi Watanabe. The other one is the case that plural records correspond to one key, and a pointer for pointing a route node of the tree structure index with record numbers of these plural records related to its key as keys, and its key are stored in a pair in the order of value. For instance, it is a leaf node LN2 related to a writer's name, Ichiro Yamada. In this case, it is unnecessary to obtain AND and it is possible to reach efficiently a target record.