Patent ID: 8208408

Claim:
A tree-based node insertion method, comprising: searching, by a memory device, in a primary tree, for a first nearest node according to a key value of a node to be inserted, wherein: a key value of the first nearest node is smaller than and most approximate to the key value of the node to be inserted, a key value of a root node of the primary tree is initialized to a minimum key value, and a key value of a left child node is greater than a key value of a parent node, the key value of the parent node is greater than a key value of a right child node, and the left child node and right child node belong to the parent node in the primary tree; specifying, by a memory device, a secondary tree, to which an external pointer of the first nearest node points, as a current secondary tree, and determining whether the current secondary tree is full, if the current secondary tree is full: selecting a node from the current secondary tree as a split node, inserting the split node into the primary tree as a new node, assigning a new secondary tree to the new node, pointing an external pointer of the new node to the new secondary tree, transferring nodes on the left of the split node to the new secondary tree, and searching for the first nearest node in the primary tree, if the current secondary tree is not full, inserting the node to be inserted into the current secondary tree.