ETRI-Knowledge Sharing Plaform

KOREAN
논문 검색
Type SCI
Year ~ Keyword

Detail

Conference Paper Batch-Construction of B+-Trees
Cited 6 time in scopus Download 0 time Share share facebook twitter linkedin kakaostory
Authors
Sang-Wook Kim, Hee-Sun Won
Issue Date
2001-03
Citation
Symposium on Applied Computing (SAC) 2001, pp.231-235
Language
English
Type
Conference Paper
DOI
https://dx.doi.org/10.1145/372202.372329
Project Code
00MC4400, Development of Internet Appliance Control Middleware, Moon Kyeong Deok
Abstract
Efficient construction of indexes is very important in bulkloading 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 an algorithm for batchconstructing the B+-tree, the most widely-used index structure in database systems. The main characteristic of our algorithm is to simultaneously process all the key values to be placed on each B+-tree page when accessing the page. This avoids the overhead due to 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. Also, we compare the performance of our algorithm with that of the previous one using repeated insertions through extensive experiments. The results show that our algorithm achieves up to 28 times performance gain over the previous one.
KSP Keywords
B+-tree, Database systems, Index structures, Performance evaluation, Performance gain