B⁺ 트리를 위한 벌크 로드

• 영문명: On Bulk-Loading B⁺ -trees
• 발행기관: 강원대학교 산업기술연구소
• 저자명: 김상욱(Sang Wook Kim) 황환규(Whan Kyu Whang)
• 간행물 정보: 『산업기술연구』vol.15, 235~244쪽, 전체 10쪽
• 주제분류: 공학 > 공학일반
• 파일형태: PDF
• 발행일자: 1995.09.30

영문 초록

In this paper, we propose a bulk-load algorithm for B⁺-trees, the most widely used index structures 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 analyze 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 in identical to the number of B⁺-tree pages. Considering that the redistribution process is an unavoidable preprocessing step for bulk-loading, 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.

목차

ABSTRACT

1. 서론

2. B⁺ 트리

3. 벌크 로드 알고리즘

4. 성능 분석

5. 결론

참고문헌