Patent ID: 8341187

Claim:
A method for storing table entries, wherein the method is implemented by a central processing unit, comprising: acquiring a storage position of a table entry in a hierarchical binary tree that comprises a first-part binary tree and second-part binary trees, wherein nodes of the first-part binary tree point to the second-part binary trees through pointers; and inserting the table entry to the hierarchical binary tree according to the storage position; wherein before the inserting of the table entry to the hierarchical binary tree according to the storage position comprises: allocating a node in the first-part binary tree and allocating one of the second-part binary trees to a first table entry when inserting the first table entry to the hierarchical binary tree, wherein the allocated node in the first-part binary tree points to the allocated second-part binary tree through one of the pointers; and inserting table entries to the allocated second-part binary tree through the pointer when continuing to insert the table entries to the hierarchical binary tree according to the storage position; wherein the node in the first-part binary tree corresponding to the second-part binary tree without available resources is an edge node in the first-part binary tree, if resources of the allocated second-part binary tree are used up: when an idle node exists near the edge node, allocating two new second-part binary trees, dividing values of the second-part binary tree without the available resources into two parts and adding the two parts to the two newly allocated second-part binary trees respectively, and setting a value of the idle node to an intermediate value of the values of the second-part binary tree without the available resources, wherein the edge node and the idle node respectively point to the two newly allocated second-part binary trees; and when no idle node exists near the edge node, searching the first-part binary tree for two consecutive nodes, allocating two new second-part binary trees, dividing the values of the second-part binary tree without the available resources into two parts and adding the two parts to the two new second-part binary trees respectively, and setting values of the two consecutive nodes in the first-part binary tree to a value of the edge node and an intermediate value of the values of the second-part binary tree without full resources respectively, wherein the two consecutive nodes in the first-part binary tree point to the newly allocated two second-part binary trees through the pointers respectively.