Fast Rebuilding B+-Trees for Index Recovery
Summary :
Rebuilding an index is an essential step for database recovery. Fast recovery of the index is a necessary condition for fast database recovery. The B+-Tree is the most popular index structure in database systems. In this paper, we present a fast B+-Tree rebuilding algorithm called Max-PL. The main idea of Max-PL is that at first it constructs a B+-Tree index structure using the pre-stored max keys of the leaf nodes, and then inserts the keys and data pointers into the index. The algorithm employs a pipelining mechanism for reading the data records and inserting the keys into the index. It also exploits parallelisms in several phases to boost the overall performance. We analyze the time complexity and space requirement of the algorithm, and perform the experimental study to compare its performance to other B+-Trees rebuilding algorithms; Sequential Insertion and Batch-Construction. The results show that our algorithm runs on average at least 670% faster than Sequential Insertion and 200% faster than Batch-Construction.
- Publication
- IEICE TRANSACTIONS on Information Vol.E89-D No.7 pp.2223-2233
- Publication Date
- 2006/07/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1093/ietisy/e89-d.7.2223
- Type of Manuscript
- PAPER
- Category
- Database
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Ig-hoon LEE, Junho SHIM, Sang-goo LEE, "Fast Rebuilding B+-Trees for Index Recovery" in IEICE TRANSACTIONS on Information,
vol. E89-D, no. 7, pp. 2223-2233, July 2006, doi: 10.1093/ietisy/e89-d.7.2223.
Abstract: Rebuilding an index is an essential step for database recovery. Fast recovery of the index is a necessary condition for fast database recovery. The B+-Tree is the most popular index structure in database systems. In this paper, we present a fast B+-Tree rebuilding algorithm called Max-PL. The main idea of Max-PL is that at first it constructs a B+-Tree index structure using the pre-stored max keys of the leaf nodes, and then inserts the keys and data pointers into the index. The algorithm employs a pipelining mechanism for reading the data records and inserting the keys into the index. It also exploits parallelisms in several phases to boost the overall performance. We analyze the time complexity and space requirement of the algorithm, and perform the experimental study to compare its performance to other B+-Trees rebuilding algorithms; Sequential Insertion and Batch-Construction. The results show that our algorithm runs on average at least 670% faster than Sequential Insertion and 200% faster than Batch-Construction.
URL: https://global.ieice.org/en_transactions/information/10.1093/ietisy/e89-d.7.2223/_p
Copy
@ARTICLE{e89-d_7_2223,
author={Ig-hoon LEE, Junho SHIM, Sang-goo LEE, },
journal={IEICE TRANSACTIONS on Information},
title={Fast Rebuilding B+-Trees for Index Recovery},
year={2006},
volume={E89-D},
number={7},
pages={2223-2233},
abstract={Rebuilding an index is an essential step for database recovery. Fast recovery of the index is a necessary condition for fast database recovery. The B+-Tree is the most popular index structure in database systems. In this paper, we present a fast B+-Tree rebuilding algorithm called Max-PL. The main idea of Max-PL is that at first it constructs a B+-Tree index structure using the pre-stored max keys of the leaf nodes, and then inserts the keys and data pointers into the index. The algorithm employs a pipelining mechanism for reading the data records and inserting the keys into the index. It also exploits parallelisms in several phases to boost the overall performance. We analyze the time complexity and space requirement of the algorithm, and perform the experimental study to compare its performance to other B+-Trees rebuilding algorithms; Sequential Insertion and Batch-Construction. The results show that our algorithm runs on average at least 670% faster than Sequential Insertion and 200% faster than Batch-Construction.},
keywords={},
doi={10.1093/ietisy/e89-d.7.2223},
ISSN={1745-1361},
month={July},}
Copy
TY - JOUR
TI - Fast Rebuilding B+-Trees for Index Recovery
T2 - IEICE TRANSACTIONS on Information
SP - 2223
EP - 2233
AU - Ig-hoon LEE
AU - Junho SHIM
AU - Sang-goo LEE
PY - 2006
DO - 10.1093/ietisy/e89-d.7.2223
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E89-D
IS - 7
JA - IEICE TRANSACTIONS on Information
Y1 - July 2006
AB - Rebuilding an index is an essential step for database recovery. Fast recovery of the index is a necessary condition for fast database recovery. The B+-Tree is the most popular index structure in database systems. In this paper, we present a fast B+-Tree rebuilding algorithm called Max-PL. The main idea of Max-PL is that at first it constructs a B+-Tree index structure using the pre-stored max keys of the leaf nodes, and then inserts the keys and data pointers into the index. The algorithm employs a pipelining mechanism for reading the data records and inserting the keys into the index. It also exploits parallelisms in several phases to boost the overall performance. We analyze the time complexity and space requirement of the algorithm, and perform the experimental study to compare its performance to other B+-Trees rebuilding algorithms; Sequential Insertion and Batch-Construction. The results show that our algorithm runs on average at least 670% faster than Sequential Insertion and 200% faster than Batch-Construction.
ER -
English
