Paper Info
Title
Fast Rebuilding B+-Trees for Index Recovery
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.
Year
DOI
Venue
2006
10.1093/ietisy/e89-d.7.2223
IEICE Transactions
Keywords
Field
DocType
fast recovery,index recovery,fast b,data pointer,database recovery,popular index structure,sequential insertion,tree index structure,database system,index reconstruction,index rebuilding,batch-construction. key words: b+-trees,index recov- ery,fast database recovery,data record,indexation,time complexity,b trees
Pointer (computer programming),Pipeline (computing),Computer science,Algorithm,Exploit,Time complexity,Database index,Data records
Journal
Volume
Issue
ISSN
E89-D
7
0916-8532
Citations 
PageRank 
References 
0
0.34
9
Authors
3
Name
Order
Citations
PageRank
Ig-hoon Lee1535.43
Junho Shim255977.12
Sang-goo Lee3832151.04