METHOD AND DEVICE FOR SEARCHING ASSOCIATIVE INFORMATION BY USING A PLURALITY OF ADDRESSES CONTAINING PREFIX

摘要

PROBLEM TO BE SOLVED: To provide a method and device for associative search which is based on a plurality of addresses containing prefix and with which high speed search and additional deletion can be efficiently performed. SOLUTION: The binary tree of a first stage is composed of first prefixes, the binary tree of a second stage is composed of second prefixes only with the first prefixes corresponding to each of leaves of the binary tree of the first stage, and information (such as pointer) specifying information with priority is held on each of leaves of the binary tree of the second stage by a linear list. Thus, information is managed and searched out of the set of addresses while using this list.