Method and apparatus using a binary search engine for searching and maintaining a distributed data structure

A binary search engine for identifying a data value associated with a search value, comprising:

• a search table having key entries for storing a respective key value and corresponding validity value;
• a data table having plural data entries for storing a respective data value, each data entry associated with a respective key entry;
• and
• a logic unit in communication with both of said search and data tables, said logic unit for searching said search table to identify a key value corresponding to a search value,
• wherein a validity entry for each of a first subset of said key entries indicates said respective data entry is invalid, and a validity entry for each of a second subset of said key entries indicates said respective data entry is invalid.

A method of retrieving a data value using a binary search on a discontinuously populated data structure, comprising the steps of:

• identifying a search value using a logic unit;
• using a binary search algorithm, by said logic unit, to locate, in a search table associated with said logic unit, a key value corresponding to said search value;
• determining, by said logic unit, if a validity indication associated with said located key value indicates that an associated data value is valid;
• retrieving said data value, by said logic unit, from a data table associated with said logic unit only if said validity indication indicates said data value is valid;
• repeating the steps of using, determining and retrieving for said search value using the logic unit if said validity indication indicates that said data value is invalid and until the step of using fails to locate said key value corresponding to said search value.