논 블록킹 검색연산을 위한 R-tree 기반의 동시성 제어 기법
A Concurrency Control Method for Non-blocking Search Operation based on R-tree
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
본 논문에서는 검색 위주의 공간 데이터베이스 시스템을 위한 R-tree 기반의 동시성 제어 기법을 제안한다. 기존의 제안된 기법들은 검색연산이 갱신연산과 동시에 수행되는 것을 막기 위해 노드에 공유 락이나 래치를 획득함으로써 갱신연산으로 인한 검색연산의 블록킹을 막을 수 없다는 문제를 가지고 있으며, 또한 R-tree같은 다차원 색인의 경우 갱신연산의 락 획득은 여러 노드에 걸쳐 일어날 수 있으며, 노드 분할과 같은 경우 오랜 시간동안 락을 획득하고 있을 수도 있기 때문에 검색연산은 장시간 블록킹이 되어야 하는 문제를 갖는다. 따라서 본 논문에서는 이러한 문제를 해결하기 위하여 노드의 엔트리들을 링크드 리스트로 연결하는 방법을 사용하여 노드에 엔트리를 삽입하고 있는 중에도 락이나 래치를 획득하지 않고 검색연산을 할 수 있는 링크드 리스트 기반의 동시성 제어 기법과, 노드 분할이 진행 중에 있는 노드에도 검색연산이 락이나 래치를 획득하지 않고 노드를 탐색할 수 있는 버전 기반의 동시성 제어 기법을 제안한다.
Abstract
In this paper, we propose a concurrency control algorithm based on R-tree for spatial database management system. The previous proposed algorithms can’t prevent problem that search operation is to be blocking during update operations. In case of multidimensional indexes like R-tree, locking of update operations may be locked to several nodes, and splitting of nodes have to lock a splitting node for a long time. Therefore search operations have to waiting a long time until update operations unlock. In this paper we propose new algorithms for lock-free search operation. First, we develop a new technique using a linked-list technique on the node. The linked-list enable lock-free search when search operations search a node. Next, we propose a new technique using a version technique. The version technique enable lock-free search on the node that update operations is to be splitting.
참고문헌 (19)
- R. Bayer, "Organization and Maintenance of Large Ordered Indexes", 1(3), pp.173~189 (1972)
- N. Beckmann, "The R*tree：An Efficient and robust access method for points and rectangles Proc. of the ACM SIGMOD Intl. Conf. on Management of Data", pp.322~331 (1990)
- S. Berchtold, "The X-tree ：An index structure for high dimensional data" (1996)
- K. Eswaren, "On the Notions of Consistency and Predicate Locks in a Database System", 19(11), pp.624~633 (1976)
- A. Guttman, "R-trees：A dynamic index structure for spatial searching Proc. ACM SIGMOD Int. Conf. on Management of Data", pp.47~57 (1984)
- H. V. Jagadish, "In Proc. of the Int. Conf. on Very Large DataBases" (1994)
- M. Kornacker, "High-Concurrency Locking in R-Trees", pp.134~145 (1995)
- M. Kornacker, "Concurrency control and recovery in GiST" (1997)
- T. J. Lehman, "A study of index structures for main memory database management systems In", pp.294~303 (1986)
- P. Lehman, "Efficient Locking for Concurrent Operations on B-Trees", 6(4) (1981)
- H. V. Lin, "The TV-tree：an index structure for high dimensional data" (1994)
- D. Lomet, "The hB-Tree：A Multiattribute Indexing Method with Good Guaranteed Performance", 15(4), pp.625~685 (1990)
- J. Nievergelt, "The Grid File：An AdaptableSymmetric Multikey File Structure^March", 9(1) (1984)
- R. Rastogi, "Logical and Physical Versioning in Main Memory Databases" (1997)
- K. V. Ravi Kanth, "Improved concurrency control techniques for multi-dimensional index structures Univ. of California at santa Barbara" (1998), Univ. of California at santa Barbara
- J. T. Robinson, "The K-D-B-Tree：A Search Structure for Large Multidimensional Dynamic Indexes", pp.10~18 (1981)
- D. White, "Similarity indexing with the SS- tree", pp.516~523 (1996)
- T. Sellis, "The R+-Tree：A Dynamic Index for Multi-Dimensional Objects" (1987)
- V. Srinivasan and M. Carey., "Performance of b-tree concurrency control algorithms", pp.416~425 (1995)