Network device storage of incremental prefix trees

A method comprising:

• storing a representation of a prefix table using entries in at least a first memory component and a second memory component;
• receiving an input key;
• identifying an action associated with a prefix, in the prefix table, that is a longest matching prefix for the input key, by at least:
• searching first entries stored in the first memory component for a longest first prefix portion that matches the input key;
• based on first information in a particular first entry that stores the longest first prefix portion, identifying a location in the second memory component to search for a second prefix portion;
• searching second entries stored at the location for a longest second prefix portion that matches the input key;
• based on second information in a particular second entry that stores the longest second prefix portion, identifying the action associated with the longest matching prefix for the input key;
• causing performance of the identified action.

One or more non-transitory computer-readable media storing instructions that, when executed by one or more computing devices, cause performance of:

• storing a representation of a prefix table using entries in at least a first memory component and a second memory component;
• receiving an input key;
• identifying an action associated with a prefix, in the prefix table, that is a longest matching prefix for the input key, by at least:
• searching first entries stored in the first memory component for a longest first prefix portion that matches the input key;
• based on first information in a particular first entry that stores the longest first prefix portion, identifying a location in the second memory component to search for a second prefix portion;
• searching second entries stored at the location for a longest second prefix portion that matches the input key;
• based on second information in a particular second entry that stores the longest second prefix portion, identifying the action associated with the longest matching prefix for the input key;
• performing the identified action.