×

Method and apparatus for performing a binary search on an expanded tree

  • US 7,610,271 B2
  • Filed: 09/10/2004
  • Issued: 10/27/2009
  • Est. Priority Date: 05/22/2000
  • Status: Expired due to Fees
First Claim
Patent Images

1. A table searching method, the method comprising the steps of:

  • providing at least one memory unit having a table of information including a plurality of data entries, with said table of information having a plurality of search keys associated with the plurality of data entries and with the plurality of search keys forming a tree structure based on a prefix length for each of the search keys;

    expanding the plurality of search keys such that each of the plurality of search keys is a lowest level search key or has two lowest level search keys associated therewith that cover a lowest level of the tree structure and bracket a range on said lowest level;

    performing a binary search of the lowest level search keys based on a search value to determine a longest prefix match; and

    outputting a data entry of said plurality of data entries based on said longest prefix match;

    wherein, in the expanding step, a lower valued one of said two lowest level search keys is increased by one to shift said bracketed range.

View all claims
  • 3 Assignments
Timeline View
Assignment View
    ×
    ×