BROWSE
Detail
Conference Paper
Batch-Construction of B+-Trees
Cited 6 time in 
Download 0 time
Share 
Download 0 time
Share
- 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
- 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