EFFICIENT HIGH PERFORMANCE SCALABLE PIPELINED SEARCHING METHOD USING VARIABLE STRIDE MULTIBIT TRIES

摘要

A method for high speed searching of a large database provides speed, throughput, and efficient memory usage comparable to TCAM-assisted searches without using dedicated processors. Successive groups of bits from a key are processed by tables in a search tree. The tables are constructed with different sizes and types according to the structure of the key and the distribution of information in the database. Each link to a subsequent table specifies both the type of the linked table and how many key bits the table will process. The tables include, but are need not be limited to, address offset tables that use bits from the key as an addressing offset to locate a result. Embodiments are implemented on pipeline processors that include internal memory units and access to external memory. Embodiments also include string compare tables, memory mapped tables, and/or instructions to continue searching on a different memory unit.