| 摘要 |
The invention provides a method and system for lookup (such as for example, lookup of message header information) that records information in a relatively large database in a relatively compact structure, while still providing for relatively rapid lookup and update. A relatively large but compact database includes a hybrid tree (or hybrid trie) structure, whereby information in denser portions of the database can be stored and retrieved from an identifiable leaf in the hybrid trie. The hybrid trie includes at least one leaf node marked to include a different data structure, whereby information in sparser portions of the database can be stored and retrieved from a more densely packed table. In a preferred embodiment, each hybrid trie node is marked as one of: a branch node, a leaf node, or a search node; each search node includes information for a sparser portion of the hybrid trie, packed into a structure capable of linear search in response to a set of packet header information (such as a destination IP address).
|
