Concurrent storage structure conversion: from B+ tree tolinear hash file

摘要

Shows that the efficient reorganization of a B+ tree fileninto a linear hash file can be done concurrently with user transactionnprocessing. This conversion is motivated by a change in databasenprocessing, in which efficient sequential and direct access werenoriginally needed, but now only efficient direct access is needed. Thisnis quite reasonable for a database system which accommodates new andnchanging applications. Several existing database systems, e.g. INGRES,nIMS and IDMS allow this type of reorganization, but the reorganizationnis performed offline. The author devises an algorithm which performs thenconversion and presents an analytic model of the conversion process. Thenauthor uses a typical database simulation model to evaluate thenreorganization scheme. The results from the analytic model are within 3%n(on the average) of the observed simulation results