Integrated search engine devices that utilize hierarchical memories containing b-trees and span prefix masks to support longest prefix match search operations

Abstract

A search engine device includes a hierarchical memory that is configured to store a b-tree of search prefixes and span prefix masks (SPMs). These SPMs are evaluated during each search operation to identify search prefixes that match an applied search key yet reside at nodes of the b-tree that are not traversed during the search operation. The search engine device also includes handle memory. This handle memory is configured to support a respective handle memory block for each search prefix within each of a plurality of nodes of the b-tree that reside at a leaf parent level within the b-tree. Each of these handle memory blocks may have sufficient capacity to support one result handle per bit within a span prefix mask associated with a corresponding search prefix. In other cases, each of these handle memory blocks may have sufficient capacity to support only M+1 handles, where M is a positive integer corresponding to a quantity of search prefixes supported by each of a plurality of leaf nodes within the b-tree.