Methods and systems for data consistent search and storage using trees

A network appliance comprising:

• a memory configured to store a first version of a plurality of records in a plurality of nodes of a first tree, the records indicating a plurality of rules that include a routing rule, a firewall rule, or a load balancing rule;
• at least one processor that is operatively coupled to the memory and is configured to:
• perform, in response to the network appliance receiving a network packet, a first search of the first tree to identify one of the nodes that matches the network packet to thereby identify one of the rules;
• and
• create a second tree that stores a second version of the records,
• wherein:
• creating the second tree begins after the first search begins and before the first search completes;
• creating the second tree includes creating a second tree root node of the second tree, creating a record node that stores a new record in the second tree, and creating an intermediate node that is in the second tree between the second tree root node and the record node;
• and
• the second tree includes a plurality of retained nodes that are in the first tree and in the second tree.

A system comprising:

• a first tree means for storing a first version of a plurality of records, the records indicating a plurality of rules that include a routing rule, a firewall rule, or a load balancing rule;
• a search means for searching, in response to receiving a network packet, the first tree means for a node matching the network packet to thereby identify one of the rules;
• a means for receiving a new data for storage in the records;
• a means for using the new data to identify a plurality of altered tree nodes and retained tree nodes of the first tree means;
• and
• a means for producing a second tree means for storing a second version of the records, the second tree means produced from the first tree means by replacing the altered tree nodes and retaining the retained tree nodes,
• wherein producing the second tree means begins after searching the first tree means and before searching the first tree means completes.