Integrated search engine devices that utilize hierarchical memories containing b-trees and span prefix masks to support longest prefix match search operations
US7747599B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | Jul 19, 2005 |
| Grant date | Jun 29, 2010 |
| Priority date | — |
| Expiry date | Jul 11, 2026 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F16/2246
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
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.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.