A search engine searches a database for key candidates having a longest matching prefix with a search key. The search engine includes first stage decoders each having a matrix of interconnected cells for identifying preliminary candidate keys in the database. The search engine also includes a second stage decoder having a matrix of interconnected cells for identifying secondary candidate keys from the preliminary candidate keys. Additionally, the search engine includes a longest candidate prefix module to determine whether one of the secondary candidate keys matches the search key. In some embodiments, the search engine includes a longest prefix match module for identifying the secondary candidate key having a longest matching prefix with the search key.