Patent ID: 8103697

Claim:
An index key update method for updating index keys of a database when new data with new index keys is supplied to replace old data with database index keys, comprising: a delta generating tree acquiring step that acquires a delta generating tree that holds index keys of the old data or new data as index keys in leaf nodes of a coupled node tree which is used in a bit string search and comprises a root node and a node pair, the node pair being a branch node and leaf node, or a pair of branch nodes, or a pair of leaf nodes located in adjacent storage areas, wherein the root node is a node that expresses a starting point of the tree and which is a leaf node when there is one node in the tree and a branch node when there are two or more nodes in the tree, the branch node includes a discrimination bit position for the search key with which the bit string search is performed and position information indicating a position of a primary node, which is one node of a node pair of a link target, and the leaf node includes an index key that is a bit string that is the target of a search, and this tree configuration enabling by repeated linking, at the branch node, to a primary node or a node at a position in a memory area adjacent thereto of a node pair of the link target from an arbitrary node of the tree as a search start node in accordance with a bit value of a search key at the discrimination bit position included in the branch node, until the leaf node is reached, an index key stored in the leaf node to be made a search result key, which is a search result using the search key of an arbitrary subtree having the search start node as its root node; a delta data generating step that searches the index keys held on the delta generating tree by all the index keys in the new data or old data as the search keys with the root node of the delta generating tree as the search start node and deletes from the delta generating tree an index key that is a search result key and matches a search key and sets as an insert key or delete key in the delta data the search key that does not match the search result key, and after the search using all the index keys in the new data or old data terminates generates in the delta data as delete keys or insert keys the index keys that are not deleted from the delta generating tree and still remain; an update target tree acquiring step that acquires an update target tree, which is a coupled node tree holding old data index keys as the index keys of leaf nodes; and an old-new index key updating step that generates a new data coupled node tree with the new data index keys as the index keys of its leaf nodes by deleting from update target tree the delete keys extracted from the delta data and inserting in the update target tree insert keys extracted from the delta data and updates the old data into the new data based on the new data coupled node tree.