Tree-based node insertion method and memory device
AssigneeHuawei Technologies Co., Ltd.
InventorsWenhua DU, Rongfeng Hong, Yi Yi
Life of this patent
Estimating the term…
Abstract
A tree-based node insertion method and a memory device are disclosed in embodiments of the present invention. The tree-based node insertion method includes: according to the key value of a node to be inserted, searching in a primary tree for the nearest node whose key value is smaller than and the most approximate to the key value of the node to be inserted; judging whether the current secondary tree is full, and if so, selecting a node from the current secondary tree as a split node, transferring all the nodes on the right of the split node in the current secondary tree to the new secondary tree, and if not, inserting the node to be inserted into the current secondary tree.
Claims17
A tree-based node insertion method, comprising:
- searching in a primary tree for the 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 the most approximate to the key value of the node to be inserted;
- and wherein:
- a key value of a root node of the primary tree is initialized to the minimum key value, 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 a secondary tree to which an external pointer of the first nearest node points as a current secondary tree, and judging 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 the 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.
A tree-based node insertion method, comprising:
- searching in a primary tree for the nearest node according to a key value of a node to be inserted, wherein a key value of the nearest node is greater than and the most approximate to the key value of the node to be inserted;
- and wherein a key value of a root node of the primary tree is initialized to the maximum key value, 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 a secondary tree to which an external pointer of the nearest node points as a current secondary tree, and judging 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 the nodes on the right of the split node to the new secondary tree, and searching for the nearest node in the primary tree;
- if the current tree is not full, inserting the node to be inserted into the current secondary tree.
A memory device, comprising:
- a secondary tree memory unit, configured to store a secondary tree;
- a primary tree memory unit, configured to store a primary tree that has a node with an external pointer pointing to the secondary tree.
Dependencies are inferred from the claim text.