摘要 |
PROBLEM TO BE SOLVED: To provide a method for searching a tree structure having small overhead and high scalability. SOLUTION: An index having a tree structure is prepared to search a set of data stored in a computer readable medium, and the set of data is associated with a leaf node of the tree structure. A Bc-link tree is used, which has a two-way list in a leaf node and has a one-way list in an internal node, the internal node is not locked in the process of searching data based on a key, the leaf node is locked when a search reaches the leaf node to perform an operation of search, insertion or delete. A memory barrier instruction is used in the insertion or delete. When the data based on the key do not exist in the reached leaf node, another leaf node connected by the two-way list to perform a search, and the reached leaf lock is unlocked. COPYRIGHT: (C)2010,JPO&INPIT |