Routing lookup method and device and method for constructing B-tree structure

A routing lookup device, comprising a routing lookup algorithm software component, a Central Processing Unit (CPU), a routing update interface component and a routing lookup hardware component, wherein

• the routing lookup algorithm software component is executed by the CPU to execute software calculation for a routing entry and issue an entry update instruction;
• the routing update interface component is configured to control, after receiving the entry update instruction issued by the routing lookup algorithm software component, write an updated entry into a memory of the routing lookup hardware component, and
• the routing lookup hardware component is configured to respond to a routing lookup request of a hardware system, and return to the hardware system a lookup result having a longest prefix matching, wherein the routing lookup hardware component is of a pipeline architecture;
• wherein the routing lookup algorithm software component comprises:
• an inserting operation sub-component, configured to respond to a routing insertion instruction of a routing forwarding system, and insert a routing entry into a Balance-Tree (B-Tree) structure;
• a deleting operation sub-component, configured to respond to a routing deletion instruction of the routing forwarding component, and delete the routing entry from the B-Tree structure;
• a software table entry memory management sub-component, configured to manage node data in a routing lookup algorithm and entry data of a result table;
• and
• an update hardware operation sub-component, configured to record in a cache, a B-Tree node and a result table entry changed in an inserting operation of the inserting operation sub-component or a deleting operation of the deleting operation sub-component, convert a software data format of the tree node into a hardware data format after the inserting operation or the deleting operation, and successively write converted hardware data and a corresponding hardware mapping address into the routing update interface component through a software and hardware interaction interface.