Concurrent file conversion between B+-tree and linear hash files

摘要

The motivation for this paper is to show that the conversion of a B+ tree file into a linear hash file and the conversion of a linear hash file into a B+ tree file can be done concurrently with user-transaction processing. The conversion process, in general, is motivated by a change in database processing requirements. For the first case, efficient sequential access and direct access are originally needed but now only efficient direct access is needed. For the second case, the opposite is true. This is quite reasonable for a database system which accommodates new and changing applications. Several existing database systems allow an off-line reorganization to support these changes. We devise an algorithm which performs a concurrent conversion for both cases and present an analytic model of the conversion process for each. We also employ a typical database simulation model to evaluate the reorganization scheme. The results from the analytic model for Case 1 are within 3% (on average) of the observed simulation results and for Case 2 are within 4% (on average) of the observed simulation results.