US 6,480,849 B1 · Efficient concurrency control method for high dimensional index structures

Abstract

A concurrency control method for a high dimensional index structure that provides efficient concurrency control method for a high dimensional index structure, which performs reinsertion of certain objects to cope with node overflow. The concurrency controlled searching method includes the following steps. First, an entry is obtained from a queue storing the root node and an object relating to the entry is selected. Second, whether a logic sequence number (LSN) of a lower level node is larger than an expected LSN stored in the upper node is determined. Third, the process moves to a neighbor node of the lower level node if the LSN is bigger than an expected LSN stored in the upper node in the second step, selects a relating object, and performs from the second step repeatedly. Fourth, an object of a node of a level corresponding to the lower level node in a reinsertion table is selected when a search on an index tree is finished if the LSN is not bigger than the expected LSN stored in the upper node in the second step.

Claims8

Dependent claims

In a concurrency control method for a high dimensional index structure applied to a database, an insertion method in which a concurrency is controlled, comprising the steps of:

a first step for searching a terminal node for inserting an object and determining whether it is possible to insert an object into a searched insertion node, comprising the further steps of:
a fourth step of determining whether the node is a terminal node;
a fifth step of obtaining a write-lock on the node when the node is a terminal node in said fourth step and then determining whether a LSN is bigger than an expected LSN;
a sixth step of computing MBR of a neighbor node of the searched terminal node when the LSN is bigger than the expected LSN in said fifth step and releasing write-lock on the searched terminal node;
a seventh step of performing repeatedly from said fifth step after replacing the neighbor node as an insertion node;
and
an eighth step of searching the terminal node in the lower level nodes when the node is not the terminal node in said fourth step;
a second step for inserting the object into the insertion node if it is possible to insert an object in said first step and adjusting a minimum bounding region(MBR);
and
a third step for processing node overflow of the insertion node if it is not possible to insert an object in said first step.

7 more elements

Dependencies are inferred from the claim text.

Efficient concurrency control method for high dimensional index structures

Life of this patent

Efficient concurrency control method for high dimensional index structures

Life of this patent

Abstract

Claims8