KR100709275B1 - A concurrency control method for non-blocking search operation based on r-tree - Google Patents

Abstract

The present invention relates to an Al-tree based concurrency control method for a non-blocking search operation. The present invention ensures fast response time of the search of a spatial object in various service environments using a spatial database system. The linked list-based concurrency control technique, which can perform update operations on the same node while the node is being read, and the version-based concurrency control technique, in which the search operation can search the index without locking or latching, According to the present invention, since the search operation of the spatial database system can proceed without blocking, the search operation in a collision-prone environment is improved by 2 to 4 times.

Spatial database management system, multidimensional index structure, concurrency control technique

Description

Al-tree-based concurrency control method for non-blocking search operation {A CONCURRENCY CONTROL METHOD FOR NON-BLOCKING SEARCH OPERATION BASED ON R-TREE}             

1 is an exemplary view showing the configuration of an R-Tree for a spatial database system of the present invention.

2 is an exemplary view showing the configuration of a non-terminal node in FIG.

3 is an exemplary view showing the configuration of a terminal node in FIG.

4 is an exemplary view showing a process of insertion change based on a linked list.

5 is an exemplary view illustrating a process of deleting and deleting based on a linked list.

6A to 6C are exemplary views illustrating a process of recycling an entry based on a linked list.

7 is an exemplary view illustrating an operation flow of version-based search (FindFirst).

8 is an exemplary view illustrating an operation flow of a version-based search (FindNext).

9 is an exemplary view showing an operation flow of version based insert.

10 is an exemplary view showing an operation flow of version-based insertion (FindLeaf).

11 is an exemplary view illustrating an operation flow of version based insertion (UpdateParent).

12 is an exemplary view showing an operation flow of version based insertion (FindLatestNode).

13 is an exemplary view showing an operation flow of version-based insertion (SplitLeafNode).

14 illustrates an operation flow of version-based insertion (SplitInternalNode).

15 is an exemplary diagram illustrating an operation flow of version-based insertion (UpdateEntry1).

16 is an exemplary view illustrating an operation flow of version-based insertion (UpdateEntry2).

17 is an exemplary view illustrating an operation flow of version based delete.

18 is an exemplary view showing an operation flow of version-based delete (DeleteParent).

<Description of the symbols for the main parts of the drawings>

100: non-terminal node 101: entry of non-terminal node

103: non-terminal header 200: terminal node

201: entry of terminal node 203: terminal header

The present invention relates to an R-tree-based concurrency control method for non-blocking search operations. In particular, the present invention provides a method for performing search operations without acquiring locks or latches even while inserting entries into nodes by connecting entries of nodes. In addition, R-tree for non-blocking search operation that guarantees faster response time in user query processing by enabling search operation to search nodes without acquiring lock or latch even for nodes in which node splitting is in progress. It relates to a method based on concurrency control.

In general, the concurrency control schemes of multidimensional indexes have been studied to acquire the minimum locks or latches in search operations. Among the concurrency control techniques of one-dimensional indexes, T-trees in which search operations search indexes without acquiring locks or latches Based concurrency control technique has been proposed.

Conventional multidimensional indexes have a problem of changing the search path. Conventional concurrency control techniques for solving the change of the search path can be divided into two types. The first is the method which does not allow the change of the searched route and the second is the change which allows the change of the searched route. But it's a way to detect changes and then fix them.

The representative technique of the first method is a lock coupling method, in which a child node is searched without acquiring a lock of the current node and then unlocking the current node before moving to the child node. This method is not suitable for the concurrency control technique of the R-Tree series, which must reflect the changed MBR (Minimum Bounding Rectangle) of the terminal node to the parent node during the insertion operation, and the lock operation is maintained for a long time due to the update operation. There is a problem of lowering the efficiency.

The second method needs a method to determine that the child node has changed and a method to correct the wrong path. The typical technique is R ^link- Tree.

R ^link- Tree uses Logical Sequence Number (LSN) to determine if a child node has changed, and solves the problem of wrong path by maintaining link between nodes. R ^link -Tree is an indexing technique that applies B ^link -Tree to a multidimensional index. Since R-Tree is characterized by no order between entries, the LSN plays the same role as the maximum key of B ^link -Tree. If the parent node's entry maintains the child node's LSN, and if the entry LSN read from the parent node is different from the node LSN stored in the child node, the same level of link is encountered until the LSN read from the parent node is encountered. Following this solves the problem of changing the search path.

This method has a problem of reducing the fan-out of the node by storing the LSN of the child nodes in the node, and reflects it using the lock coupling method to reflect the parent node when the MBR of the terminal node is changed. Because of this, there is a problem of reducing the efficiency of the search operation.

In the above-mentioned multidimensional concurrency control schemes, a search operation must acquire a lock or latch at least once in a node and search an index, which leads to a long search time of the node. In the past, a concurrency control scheme for one-dimensional indexes has been proposed that allows search operations to search indexes without acquiring locks or latches. This solves the problem that the search operation must acquire a lock or latch by using a method of copying the entries of the node to a new node and then inserting the entry in the copied node when the update operation tries to insert an entry in the node.

However, such a technique has a problem that additional garbage is deleted because many garbage nodes are generated one by one because of one insertion operation.

The present invention has been proposed to solve the problems of the prior art, and an object of the present invention is to generate a new version only at the time of partitioning and not to generate a new version every time an insert operation inserts an entry into a node. It is to provide an R-tree based concurrency control method for non-blocking search operation that can solve the problem caused by excessive garbage nodes by performing partitioning.

Another object of the present invention is a non-blocking search operation that ensures fast response time in a search-oriented spatial database system by using a structure that does not request locks or latches when searching for nodes by connecting entries of each node to a linked list. An R-tree based concurrency control method is provided for the present invention.

The R-tree based concurrency control method for the non-blocking search operation of the present invention for achieving the object of the present invention, in the R-tree-based concurrency control method for a multi-dimensional index, linked between each entry of the node structure It includes a list structure, and adjusts the order of constructing the linked list upon entry insertion, deletion, and modification so that the search operation can process the operation without acquiring locks or latches.

In addition, the R-tree-based concurrency-controlled entry recycling method for the non-blocking search operation of the present invention for achieving the above object is maintained after each index, and after the link is released for deletion operation, A global entry deletion factor that is incremented and used to maintain the increased value in the entry of the node; A local entry deletion factor, which is maintained in the index operation table with a value recording the most recent global entry deletion factor before performing a predetermined operation, and maintained one by one for each operation; And an index operation table for managing operations being performed on the index. An R-tree-based concurrency-controlled entry recycling method for recycling an entry marked for deletion using the method, wherein the recycling of entries is performed by deleting a predetermined node. Comparing the minimum local entry deletion coefficient among the local entry deletion coefficients of the index operation table with the size of the global entry deletion coefficient of the node when performing an insert operation with a global entry deletion coefficient stored in the index operation table; And if the global entry deletion factor is greater than a local entry deletion factor, without inserting directly into the deleted node, checking whether insertion is possible for the next entries of the node to be inserted, and performing an insert operation on the insertable node. Characterized in that consisting of;
In addition, the R-tree-based concurrency control method for the non-blocking search operation of the present invention for achieving the above object, in the method for generating a version to control the R-tree-based concurrency, insert operation is entered in the node It is characterized in that the new version is generated only at the time of splitting without creating a new version every time the insert is inserted, and the splitting is performed using the generated version.
In order to achieve the above object, the R-tree-based concurrency-controlled deletion method for the non-blocking search operation of the present invention, in deleting an entry, searches for a terminal node with an entry to be deleted and searches for an entry in the corresponding terminal node. The terminal node having an entry to be deleted may be deleted by simultaneously using a deletion stack storing a path to the terminal node and a search stack storing entries overlapping with the entry to be deleted.

delete

Hereinafter, exemplary embodiments of the present invention will be described in detail with reference to the accompanying drawings. However, the following examples are merely to illustrate the present invention is not limited to the contents of the present invention.
Although the present invention is not shown, a spatial database includes a search engine that retrieves query results from a database for a user query input through a query processor, and a concurrency control unit for performing concurrency control functions such as insertion and deletion of objects. Implemented on the system.

1 is an exemplary view showing the configuration of an R-Tree for a spatial database system of the present invention.

As shown, the R-Tree for the spatial database system according to the present invention is composed of a non-terminal node 100 and a terminal node 200. The non-terminal node 100 includes a non-terminal entry 101, and the terminal node 200 includes a terminal entry 201.

FIG. 2 is a diagram illustrating a configuration of a non-terminal node in FIG. 1, wherein the non-terminal node 100 includes a non-terminal header 103 and a non-terminal entry 101, and is connected to a linked list between entries.

3 is a diagram illustrating a configuration of a terminal node in FIG. 1, wherein the terminal node 200 includes a terminal header 203 and a terminal entry 201, and is connected to a linked list between entries.

In the structure of FIGS. 2 and 3 as described above, the insert operation guarantees a unit operation. Because the size of the link has the size to match the word alignment, and the link linking operation is possible with one instruction, the interrupt cannot occur during link linking operation. .

4 illustrates an example of a linked list-based insertion change process, FIG. 4A illustrates a state of a node before inserting an entry, and FIG. 4B illustrates a state of inserting a new entry.

As shown, three nodes are used in a node that can have up to five entries, and two nodes are empty (300: the active node consists of a linked list of sltFst, and the empty node is a sltFree First, insert the contents of the entry to be inserted into entry 4, connect entry 4 to entry 3, then connect entry 2 to entry 4, and perform an insert operation between entry 2 and entry 3. Thereafter, four nodes are used in a node that can have a maximum of five entries, and one node becomes empty (400). sltFst refers to the first slot of the node, and sltFree refers to the first empty slot of the node. ① Find an empty slot and copy the object identification number (OID) and minimum bounding rectangle (MBR). ② connect the data link of entry 3 and entry 4, and ③ finally connect entry 2 to entry 4. If the process of ③ occurs before ②, the search operation can read entry 4, and the entry 3 cannot be read because the link to entry 3 is not yet connected. Therefore, the same process as ② should be performed before ③.

In other words, by connecting in the above order, a new entry (Entry4) can be inserted between entry 2 and entry 3, and in this order, the search operation can be performed without any problem even when adding a new entry to the node. There is an advantage.

5 is a diagram illustrating a process of a change of deletion based on a linked list, and shows a state of a node after deleting entry 2. FIG.

In other words, the state of FIG. 4A becomes the state of FIG. 4B and the state of FIG. 5, whereby three nodes are used in a node that can have up to five entries, and two nodes are empty 300. After the entry 2 is deleted, two entries are used in a node having up to five entries, and three nodes become empty (500).

That is, ① find the slot to delete and ② connect entry1 and entry3. If you break the data link between entry 2 and entry 3, you should not release the data link between entry 2 and entry 3, because the search operation that is already reading entry 2 before you delete it will not move to entry 3.

The delete operation is performed by simply marking a delete on the entry.

FIG. 6 illustrates an example of a linked list-based entry recycling process. FIG. 6 illustrates reuse of entries marked for deletion by FIG. 5.

6 shows a process for insertion after deletion using an Entry Delete Sequence Number (EDSN). The fundamental problem with entry reuse is that deleted entries cannot be reused because the search operation may be reading about deleted entries. Thus, the present invention considers a method for ensuring that a search operation is not reading on deleted entries.

This problem is solved by using an index operation table (IOT) that maintains the entry deletion coefficient in each entry of the node and manages the operations being performed on the index. EDSN is a sequentially increasing value, and there is a global entry deletion coefficient (G-EDSN) and a local entry deletion coefficient (L-EDSN: Local EDSN).

One G-EDSN is maintained for each index. The G-EDSN is incremented after the link is released for the delete operation. The G-EDSN is used to store the increased G-EDSN in the entry.

The L-EDSN is a value that records the most recent G-EDSN before performing an operation. The L-EDSN is maintained in the IOT, one for each operation.

The lifetime of operations managed in the IOT is until one node is searched and terminated. To discover the next node, the new G-EDSN must be copied to the L-EDSN of the IOT. This is to speed up entry reuse by making the life cycle of operations very short. L-EDSN of update operations except search operation is ∞. The L-EDSN checks the EDSN of the entry to be inserted when the insert operation is performed, and if there is an operation in the IOT with an L-EDSN smaller than the EDSN, the entry may be the entry being searched for by the search operation. Used to not insert. The EDSN initial value of each entry is -∞.

In FIG. 6A, the initial G-EDSN is 5, and three operations are executed at the same time. O1 has an L-EDSN value of 5 and performs a search operation. Suppose that O2 deletes, O3 inserts, and O1 compares keys against R2. At this time, if O2 deletes R2, first releases the link from R1 to R2, and then stores the EDSN of R2 as 6, which is an increase value of G-EDSN.

6B shows a state in which R2 is deleted and an EDSN is stored. Next, if the insert operation is performed in the state of FIG. 6B, sltFree points to R2 and will try to insert into R2. However, since the EDSN 6 of R2 is larger than the minimum L-EDSN of 5 among the L-EDSNs of the IOT, it should not be inserted into R2. A small EDSN should not be inserted into the entry because it has the possibility that some of the operations may have been searching for the entry before unlinking it by the delete operation. Therefore, each entry is connected as shown in FIG. 6C. If O1 performs an insert operation after finishing the operation, it can be inserted into R2.

7 is a diagram illustrating an operation flow of a version-based search (FindFirst), the search (FindFirst) is a process of finding the first entry belonging to the query range. The first entry is found by pushing the root node onto the stack and looking for an entry.

That is, after putting a lotnode into the search stack (step 701), it checks if the search stack is empty (step 702), exits if the search stack is empty, and pulls out one item from the search stack if it is not empty (step 703). ,

Thereafter, it is determined whether it is a record identification number (RID) (step 704), and if it is determined that the RID is returned (step 708), the process proceeds to step (702). If it is determined that the MBRs of the overlap do not overlap (step 706), and if it is determined that there is no overlap (step 706), it moves to another entry (step 705) and performs step 706 again. Proceed to step 705.

8 is a diagram illustrating an operation flow of a version-based search (FindNext), the search (FindNext) iterates until the stack is empty while iterating through the nodes.

In other words, the search stack is checked for empty (step 801), if it is empty, it exits, and if it is not empty, one item is taken out of the search stack (step 802). If the RID is determined (step 803), if the RID is returned (step 806), the process proceeds to step 801, and if it is not the RID, it is determined whether the MBR to be searched and the MBR of the current entry overlap (step 805). If it is determined that there is no overlap (step 804), it moves to another entry and performs step 805 again. If it is determined to overlap, one item is inserted into the search stack (step 806) and the process proceeds to step 804.

FIG. 9 is an exemplary view illustrating an operation flow of a version-based Insert. Insert may be divided into a FindLeaf process of finding a terminal node to insert an object and a process of inserting an object into the terminal node. .

Retry value to be returned to the terminal node split is set first to True (step 901). If the retry value is True, the insertion is terminated and if it is False (Step 902). Set Tri to Fall (step 903) and then perform FindLeaf (step 904). One item is taken out from the insertion stack used during the FindLeaf process, which is a terminal node (step 905). Since it is necessary to insert the terminal node, it is determined whether the node is full (step 906), and if it is full, step 907 is performed. Otherwise, an entry is directly inserted into the terminal node (step 908).

If splitting occurs first (step 907), the result is set in the retry, and if this value is true (step 911), this terminal node is versioned and added to the garbage collector (step 912) otherwise terminal node lock. Is released (step 913) and ends.

Next, when the terminal node is directly inserted (step 908), when the representative MBR of the insertion is changed, an insertion (UpdataParent) (step 910) is performed. Otherwise, the terminal node lock is released (step 913), and the process ends.

FIG. 10 is an exemplary view illustrating an operation flow of version-based insertion (FindLeaf) and finding a terminal node to be inserted when performing an insertion operation.

10, insertion (step 904) searches for an index in the direction of the terminal node, looking for an entry that can increase the MBR of the non-terminal node to the minimum (step 1006), and terminates the function if it encounters the terminal node (step 1003). do. The insertion (step 904) performs a process of stacking the searched non-terminal node and the terminal node on the stack while searching for the terminal node, which expands the MBR of the parent node (step 910) or the splitting of the node occurs. In that case (step 907). If the node is versioned as in step 1004, then the node has been partitioned by another operation while waiting to acquire the lock of the node. In this case, the parent node is searched again using the stack 1007.

FIG. 11 illustrates an operation flow of version-based insertion (UpdateParent). In FIG. 9, when the MBR of parent nodes is to be changed due to the insertion operation, the parent nodes are removed from the stack one by one.

Referring to FIG. 11, the MBR of the parent node is expanded (step 910) during the insertion operation. Insertion (UpdateParent) moves to the parent node direction using the stack (step 1102) and changes the entry MBR of the parent node (step 1104) when the node MBR of the child node is changed. If the parent nodes stored in the stack are versioned, the findLatestNode function is called to find the latest version for the versioned node (step 1103). The latest version is found and the entry MBR of the node is changed using insert (UpdateEntry1) (step 1104). Insertion (UpdateParent) may have an empty entry in the node due to an entry reuse problem, but can not insert. In this case, you can pass control to another operation for a while and wait until you have finished retrying to re-use the entry.

A search operation is an operation that does not require a lock or latch, and since the L-EDSN of the search operation written to the IOT has a very short life cycle, UpdateParent can reuse an entry without waiting for a long time.

FIG. 12A illustrates an operation flow of version-based insertion (FindLatestNode), and FIG. 12B illustrates a diagram for better understanding of FIG. 12A.

In case of splitting after simple insertion or insertion of a child node, the corresponding entry of the child node in the parent node should be changed.In this case, when the node stored in the stack and known as the parent is split, the entry is moved to another node next to it. This is the process of finding the appropriate node in preparation for it.

In other words, the FindLatestNode function searches for the latest non-versioned node including the entry of the pointer. In FIG. 12B, if N ₃ is versioned, the search space to be searched is N ₅ and N ₆ , so the latest version having the entry to be searched while moving to N ₅ and N ₆ along the right link of N ₃ is found. Find.

13A and 13B are diagrams illustrating an operation flow of version-based insertion (SplitLeafNode), in which case a suitable terminal node to be inserted is found, but the corresponding node is full and the node needs to be split. It also includes the process of splitting node entries and changing the parent node's MBR.

Referring to FIG. 13, insertion (SplitLeafNode) is a process of splitting a terminal node. Basically, the partitioning process uses a version-based partitioning technique that leaves the nodes to be split and creates two new nodes without changing the state of the nodes before splitting.

If the node to be split is a terminal node, a rectangle (Rect: Rectangle) is inserted into an appropriate node after splitting. SplitLeafNode starts after acquiring locks for the left and right nodes of the node, respectively (steps 1307 and 1308). The order of acquiring the locks of nodes is always obtained from left to right. If not, a deadlock with another operation can occur while acquiring the lock. Thus, as in step 1303, the node is unlocked and the lock is acquired from the left to the right direction. After holding the lock, we need to verify that the node is versioned (step 1305), and if so, restart the insertion process. This is when the node is unlocked (step 1306), the left node connected to the node is found, and the node is locked again. If the node is a version, the node is divided by another insert operation. Therefore, insert operation is performed again because the node should not be divided. Create two new nodes (step 1315), connect the links to each other (step 1317), and insert a rectangle into the most suitable node of the two nodes (step 1318). All that remains of the insert operation is to insert the MBR and the pointer of the new node to the parent node (step 1326). If there is no empty entry in the parent node, split the parent node using SplitInternalNode (step 1333), otherwise insert an entry in the parent node, if the parent node's MBR is changed (step 1327). By calling Insert (UpdateParent) (step 1328), the entry MBR of the parent node pointing to the parent node must be changed. Since the stack is empty at step 1320 indicates that the node is a root node, create a node for the new root node (step 1322), then replace the root node pointer with the new root node and indicate that the existing root node is versioned. (Step 1324). If the stack is not empty, an entry is required to be inserted into the parent node, so a node is popped from the stack, and the latest node of the popped node is stored as a parent (step 1321). If there is an empty entry in the found node (step 1326), the node is split (step 1333). Finally, as shown in step 1329, connect the left and right nodes pointed to by the node before the split, and connect the right link of the split node to the newly created left node (step 1329). To be found.

14A and 14B are diagrams illustrating an operation flow of version-based insertion (SplitInternalNode), and a case where a non-terminal node, rather than a terminal node, needs to be split.

According to FIG. 14, if a node to be split is a non-terminal node, two entries for two newly created child nodes are inserted after splitting. The whole process is similar to SplitLeafNode, except for inserting an entry into a node. SplitLeafNode finds a suitable node to insert and inserts an entry, while SplitInternalNode finds a node containing a split node among newly created nodes and inserts two child nodes into the found node. Step 1418).

FIG. 15A illustrates an operation flow of version-based insertion (UpdateEntry1), and illustrates a state in which a parent node changes an MBR when a representative MBR including all MBRs of a child node is changed during an insert operation. . The change of entry is accomplished by assigning a new entry and setting a pointer to the existing entry to point to the newly allocated entry.

According to Fig. 15B, the change operation on the entry of the node is an operation of changing the MBR of the entry or changing the node pointer of the entry. Since the change operation changes the contents of the entry while the search operation searches for the node without locking or latching, the unit operation cannot be guaranteed, so the present invention uses a method of performing the change operation by the insert operation and the delete operation of the entry. If the entry to be inserted in step 1502 is R4 and the entry to be deleted is R2, the link of R4 and R3 is first connected as shown in FIG. 15B (1) and then the R1 and R4 are connected (2). Ensure that you can search without problems.

FIG. 16A illustrates an operation flow of version-based insertion (UpdateEntry2). FIG. 16A illustrates an example in which a terminal node is divided and two child nodes are generated due to an insertion operation to insert two entries into a parent node at once.

According to FIG. 16B, the insert (UpdateEntry2) could be completed by inserting only one new entry in the existing partitioning scheme. However, in the partitioning scheme of the present invention, since two new nodes are created, the node before splitting was indicated. The operation of inserting a new entry at the same time as changing the entry to an entry pointing to a new node should be performed by the unit operation. This operation is handled by inserting two new entries (step 1602) and deleting existing entries (step 1603). Step 1604 describes this process. In FIG. 16B, if the entries to be inserted are R4 and R5 and the entries to be deleted are R2, the search operation is performed by first connecting (2) the links of R4, R5 (1) and R3, and then connecting (3) the R1 and R4. Ensure that you can search without any problem.

FIG. 17 is a view illustrating an operation flow of version-based deletion, which is a process of finding an appropriate terminal node having an entry to be deleted and deleting an entry in the corresponding node. This method describes how to use the delete stack at the same time. This process is for the case where there is no remaining entry in the node when the entry is deleted.

According to FIG. 17, the delete operation uses two stacks. The search stack is a stack to find the entry to delete, and the delete stack is used to reflect the parent node when the node's MBR is changed after deleting the entry to the node. The delete operation finds the terminal node with the entry to be deleted (step 1715) and then deletes the entry (step 1704). If the MBR of the node which deleted the entry is reduced (step 1708), an operation of changing the entry MBR of the parent node is performed (step 1709). If all entries of the node are deleted, the node is deleted and the entry of the parent node pointing to the deleted node is deleted (step 1706). However, deleting a node should not delete the node immediately because the search operation may be searching for the node to delete.

  The delete operation finds the object to be deleted and the entry to be deleted using the object's MBR. The method of using the stack to find the terminal node in the delete operation is a combination of using the stack to find the entries to search in the search operation and using the stack to find the terminal node to insert in the insert operation. Similar to one method. This may occur when the MBRs of the nodes overlap in the R-tree structure, so that the deleted entry can be found only by searching for multiple terminal nodes. Therefore, in the present invention, two stacks are used to find an entry to delete. Whenever you pop a search stack, you can push it to the delete stack. However, since the delete stack is a stack for storing paths to terminal nodes, there should not be multiple nodes of the same level in the deletion stack. Therefore, when pushing to the delete stack, the level of the nodes in the delete stack must be checked (step 1712). The level of the node increases by one as the depth of the index increases. That is, the root has the smallest value and the terminal nodes have the largest value. If there is a level in the delete stack that is higher than the level of the node popped from the search stack, this problem is resolved by popping the delete stack until a low level is reached (step 1713). If the node that popped the search stack in step 1715 is the terminal node, the node is popped in the delete stack (step 1718) to remove the node from the path to the terminal node, and it is checked whether the entry to be deleted exists in the node (step 1917). ). If the entry to be deleted is not found, the next node is searched using the search stack (step 1722). Eventually, if a terminal node to be deleted is found, a path to the terminal node other than the terminal node remains in the deletion stack. If there is no entry in the node after deleting the entry in step 1704, the node must be deleted, and the entry indicating the node of the parent node to be deleted must be deleted (step 1706).

18 is an exemplary diagram illustrating an operation flow of a version-based deletePaper.

Referring to FIG. 18, after deleting an entry in the delete operation (Step 1704), if there is no entry in the node, the parent node is deleted using the DeleteParent function. If at least one entry remains, only the MBR of the parent node is changed (step 1810). The process of finding the parent node whose entry is to be deleted in DeleteParent is the same as finding the parent node whose entry is to be changed in UpdateParent. If an entry is found, the entry is deleted (step 1804) and applied to the parent node in the same manner.

As described above, although described with reference to a preferred embodiment of the present invention, those skilled in the art various modifications of the present invention without departing from the spirit and scope of the invention described in the claims below Or it may be modified.

  As described above, the present invention is a concurrency control technique in which a search operation can search an index without applying any locks or latches in consideration of the fact that a multidimensional index has a higher frequency of search operations than an update operation. Links the entries in the node to a linked list so that update operations can occur while searching for nodes, and when performing node partitioning, use a version-based partitioning technique to obtain nodes without obtaining locks or latches on the node where the search operation is partitioned. By searching, the service can guarantee faster response time for spatial search query request in the environment where various types of geographic information services using spatial database system are provided through internet.

Claims (11)

In the concurrency control method for a multidimensional index, Includes a linked list structure between each entry of the node structure, and adjusts the order of constructing the linked list when an entry is inserted, deleted, or changed so that a search operation can process the operation without acquiring a lock or latch. R-tree-based concurrency control method for non-blocking search operation. The method of claim 1, wherein the entry insertion is Finding the first empty slot of the node; Connecting a data link of an entry to be inserted with an entry next to the position at which the entry is to be inserted; And Concatenating the entry to be inserted with the entry immediately preceding the position at which the entry is to be inserted; R-tree-based concurrency control method for a non-blocking search operation, characterized in that consisting of. The method of claim 1, wherein deleting the entry Finding a slot to delete and writing a delete mark to the entry to be deleted; And Concatenating entries before and after the entry to be deleted; R-tree-based concurrency control method for a non-blocking search operation, characterized in that consisting of. A global entry deletion factor used to maintain the incremented value in the entry of the node after unlinking, maintaining one per index; A local entry deletion factor, which is maintained in the index operation table with a value recording the most recent global entry deletion factor before performing a predetermined operation, and maintained one by one for each operation; And an index operation table for managing operations performed on the index; an R-tree-based concurrency controlled entry recycling method for recycling an entry marked for deletion using the index operation table. Recycling an entry is performed when an insert operation is performed while a predetermined node is deleted and the global entry deletion count for the node is stored. Comparing the minimum local entry deletion coefficient among the local entry deletion coefficients of the index operation table with the size of the global entry deletion coefficient of the node; And If the global entry deletion factor is greater than the local entry deletion factor, performing an insert operation on the insertable node by checking whether insertion is possible to the next entries of the node to be inserted without immediately inserting the deleted node; ; R-tree based concurrency controlled entry recycling method for non-blocking search operation, characterized in that consisting of. 5. The R-tree based concurrency controlled entry for non-blocking search operations according to claim 4, wherein the recycling of the entries can be performed when any search operation is determined to be impossible to read the entry. Recycling method. In generating a version to control R-tree based concurrency, R-tree for non-blocking search operation, characterized in that insert operation creates a new version only at partitioning without creating a new version every time an entry is inserted into a node, and performs partitioning using the created version. Based concurrency control method. The terminal node of claim 6, wherein the terminal node to be inserted when the insert operation is performed is performed. R-tree for non-blocking search operation, which goes through several parent nodes and finds whether it is the MBR and version of each node or whether the corresponding node is the root node, and proceeds by putting the nodes on the stack. Based concurrency control method. The method of claim 7, wherein when the terminal node to be inserted is found but the corresponding node is full, the node must be divided. Creating two new nodes; And Changing MBRs of parent nodes by dividing entries of a corresponding node among the generated nodes; R-tree based concurrency control method for the non-blocking search operation, characterized in that for performing. 8. The method of claim 7, wherein the MBR of the corresponding entry in the parent node is changed when the representative MBR including all MBRs of the child node is changed during the insert operation. Receiving a new entry; And Setting a pointer to an existing entry to point to the newly allocated entry; R-tree-based concurrency control method for a non-blocking search operation, characterized in that performed by performing. In deleting entries, The terminal node with the entry to be deleted is found and the entry is deleted within the terminal node. The terminal node with the entry to be deleted has a deletion stack storing a path to the terminal node and an entry overlapping the entry to be deleted. An R-tree based concurrency controlled deletion method for a non-blocking search operation, characterized by searching using the search stack simultaneously. The method of claim 10, further comprising: searching for a parent node of a corresponding terminal node and finding an entry indicating a corresponding terminal node of a parent node in deleting the entry; Deleting the entry and checking whether the parent node is empty; If the parent node is not empty, reflecting the change of the representative MBR of the parent node to the parent node; And Deleting the parent node and recycling the parent node when the parent node becomes empty; R-tree-based concurrency controlled deletion method for the non-blocking search operation, characterized in that for performing.

Images