B+ 트리의 일괄 구성 : 알고리즘 및 성능 분석 = Batch-Construction of B+-trees: Algorithm and Its Performance Analysis

국문 초록 (Abstract)

데이타베이스를 구축하는 경우나 데이타베이스내에 새로운 인덱스를 구성하는 경우에는 방대한 양의 객체들을 대상으로 하므로 인덱스의 효율적인 구성은 매우 중요하다. 본 논문에서는 데이타베이스 인덱스 구조로 가장 널리 사용되는 B^+ 트리를 위한 일괄 구성 알고리즘을 제안한다. 제안된 일괄 구성 알고리즘에서는 B^+ 트리 구성에 필요한 각 페이지를 디스크로부터 한번 액세스할 때, 이곳에 저장될 모든 키 값들을 한꺼번에 처리하는 방식을 사용한다. 따라서 기존의 삽입 알고리즘을 반복적으로 적용함으로써 B^+ 트리를 구성하는 경우 같은 페이지를 디스크로부터 여러번 액세스하게 되는 오버헤드를 제거할 수 있다. 성능 분석을 위하여 본 알고리즘의 수행시 발생되는 디스크 액세스 수를 분석하였다. 분석 결과에 의하면, 재배치 작업에서 발생하는 디스크 액세스를 제외하면, B^+ 트리 구성에 사용되는 페이지 수 만큼의 디스크 쓰기가 발생하는 것으로 나타났다. 재배치 작업이 일괄 구성을 위한 필수적인 전처리 단계라는 점을 고려 하면, 각 페이지당 한번의 디스크 액세스만을 요구하는 본 알고리즘은 일괄 구성을 위한 최적의 알고리즘 이라 할 수 있다. 또한, 시뮬레이션을 통하여 각 인자들의 값의 변화에 따르는 성능상의 경향을 제시하였으며, 삽입 알고리즘을 반복적으로 적용하는 기존의 경우와의 실험적인 비교를 통하여 제안된 알고리즘을 사용하는 경우의 성능 개선 효과를 제시하였다.

다국어 초록 (Multilingual Abstract)

The efficient construction of indexes is very important in bulk-loading a database or adding a new index to an existing database since both of them should handle an enormous volume of data. In this paper, we propose a batch-construction algorithm for the B^+-tree, the most widely used index structure in database systems. The main characteristic of our algorithm is to simultaneously process all the keys to be placed on each B^+-tree page when accessing the page. This avoids the overhead for accessing the same page multiple times, which results from applying the B^+-tree insertion algorithm repeatedly. For performance evaluation, we have analyzed our algorithm in terms of the number of disk accesses. The results show that the number of disk accesses excluding those in the redistribution process is identical to the number of B^+-tree pages. Considering that the redistribution process is an unavoidable preprocesing step for batch-constructing of B^+-trees, our algorithm requires just one disk access per B^+-tree page, and therefore turns out to be optimal. We also present performance tendancy according to the changes of parameter values via simulation. Finally, we show the performance enhancement effect of our algorithm compared with the one using multiple insertions through experiments.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. B+ 트리
• 3. 일괄 구성 알고리즘
• 4. 성능 분석
• 5. 결론
• 참고문헌