Multilevel Data Structures Models and Performance

Abstract

We advocate a stepwise method of deriving high performance implementation of a set of operations. This method is based on the ability to organize the data into a multilevel data structure so as to provide an efficient implementation of all the operations. Typically, for such data organization the performance may deteriorate over a period of time and that can be corrected by reorganizing the data. This data reorganization is done by the introduction of maintenance processes. For a particular example we consider the multilevel data organization and the different models of maintenance processes possible. We sketch a correctness proof for the implementation we develop. Performance behaviour for the different models are derived and we also present some simulation studies of the performance.