Patent ID: 7603346

Claim:
A pipelined search engine device, comprising: a hierarchical memory configured to store a b−tree of search prefixes at multiple levels therein that reside at corresponding stages of the pipelined search engine device and are sequentially accessed during a search operation; a pipelined tree maintenance engine embedded within the search engine device, said pipelined tree maintenance engine comprising a plurality of node maintenance sub-engines distributed with the multiple levels of said hierarchical memory; and a pipeline control and a search logic distributed with the multiple levels of said hierarchical memory; wherein the pipelined control and search logic is 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.