Patent ID: 7747599

Claim:
An integrated circuit search engine device, comprising: a hierarchical memory configured to store a b-tree of search prefixes and span prefix masks therein, said span prefix masks having values that are evaluated during a search operation to identify one or more search prefixes that match an applied search key yet reside at least one node of the b-tree that is not traversed during the search operation; and search logic configured to search the b-tree of search prefixes in said hierarchical memory by evaluating at least one search prefix and corresponding span prefix mask at a first node of the b-tree within a search path of the b-tree during the search operation to thereby identify any prefixes that match the applied search key yet reside at a second node of the b-tree that is lower in the b-tree relative to the first node and outside the search path of the b-tree when the b-tree is traversed during the search operation.