상호 협동적 잠금 규약을 이용한 B link-트리 동시성 제어 기법 = A B link-Tree Concurrency Control Method using Cooperative Locking Protocol

국문 초록 (Abstract)

B-트리의 동시성을 높이기 위한 연구중에서 B^(link)-트리를 이용한 동시성 제어 기법이 많은 관심을 받아왔다. B^(link)-트리를 이용하는 기법은 다른 알고리즘과 비교하여 제공하는 동시성의 정도가 매우 높은 특성을 보이는 반면 키 삭제자의 트리 재구성 동작이 지원되지 않았던 문제가 있었다. 본 논문에서는 기존 B^(link)-트리를 이용한 알고리즘이 갖는 정도의 동시성을 보장하는 동시에 삭제자의 트리 재구성 동작을 허용하는 새로운 B^(link)-트리 동시성 제어 기법을 소개한다. 논문에서는 효과적인 B^(link)-트리 동시성 제어를 위해 상호 협동적인 잠금규약과 트리 재구성을 위한 노드 갱신 규칙을 이용한다. 제안되는 기법에서는 트리 재구성 작업이 다른 프로세스의 탐색 연산과 함께 진행될 수 있으며 알고리즘 수행중에 교착상태가 발생하지 않는다.

다국어 초록 (Multilingual Abstract)

For the purpose of improving B-tree concurrency, a number of algorithms have been proposed Among the previous works, the algorithms based on B^(link)-tree draw much attention, While such B^(link)-tree algorithms, in general, guarantee higher concurrency than others that do not use B^(link)-tree, they do not provide an efficient mechanism to reconstruct underflowed nodes. In this paper we present a new concurrency control method based on B^(link)-tree that provides high concurrency and an efficient reconstruction mechanism. A new locking protocol, called cooperative locking protocol, and a node modification rule for tree reconstruction are main contributions. In the proposed method, the tree reconstruction operations can concurrently proceed with search operations and any concurrent operations never result in deadlock.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. B^(link)-트리 구조
• 3. 잠금 모델
• 4. 트리 탐색을 위한 프로시져
• 5. 키 삽입자의 트리 재구성 동작
• 6. 키 삭제자의 트리 재구성 동작
• 7. 트리 재구성을 위한 노드 갱신 방법
• 8. 교착상태 무발생의 증명
• 9. 알고리즘 성능 고찰
• 10. 결론
• 참고문헌
• 저자소개