BULK_ADD : B^+ - 트리에 다수의 키값을 추가하기 위한 새로운 전략 = BULK_ADD : A New Strategy for Adding Multiple Keys into a B^+ - tree

국문 초록 (Abstract)

B^+-트리는 화일에 저장된 정보를 빠르게 검색하기 위한 인덱스 방법으로 널리 사용되고 있다. 정보 검색 분야나 웹 서버 등에서는 이미 인덱스를 가지고 있는 화일에 여러 개의 데이터를 한꺼번에 입력하거나 다른 화일을 병합하는 연산이 빈번하게 요구된다. 이러한 병합 연산은 기존 인덱스에 새로운 다수의 키값들을 삽입하는 동작을 요구하므로 삽입 또는 병합할 데이터가 많을 경우 처리 시간이 많이 소요된다. 이러한 문제점을 해결하기 위하여 이 논문에서는 이미 구성되어 있는 B^+-트리와 삽입되어질 데이터 집합을 병합하여 새로운 B^+-트리를 생성하는 BULK_ADD 전략을 제시하였다. 또한, 제안된 BULK_ADD 전략을 구현하여 B^+-트리에 반복적으로 삽입하는 방법과 성능을 비교 분석하였다. 성능 분석 결과 기존 인덱스의 크기에 대해 삽입될 객체의 수가 일정 비율(약 0.4%) 이상이 되면 B^+-트리의 반복적인 삽입기법에 비해서 BULK_ADD 전략이 매우 우수한 성능을 가지는 것으로 나타났다. 이 비율은 정보 검색 시스템이나 웹 서버 등에서 새롭게 수집된 자료의 양에 따라 B^+-트리 병합 시간을 최소화하기 위한 방법을 선택하는 기준으로 사용할 수 있다. 동시에 일정 시간 내에 새롭게 수집되는 자료의 양을 예측할 수 있는 경우 그 인덱스를 새롭게 갱신하는 주기를 이 비율에 근거하여 결정할 수 있기 때문에 최소한의 오버헤드로 최신의 정보를 유지하는 인덱스를 구성할 수 있다.

목차 (Table of Contents)

• 요약
• 1. 서론
• 2. B^+ - 트리의 일괄 구성 알고리즘
• 3. BULK_ADD 전략
• 4. 결론
• References