Multilevel data structures: models and performance

A stepwise method of deriving the high-performance implementation of a set of operations is proposed. This method is based on the ability to organize the data into a multilevel data structure 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, the multilevel data organization and the different models of maintenance processes possible are considered. The various models of maintenance process provide varying amounts of concurrency by varying the degree of atomicity in different operations. Performance behavior for the different models is derived and a correctness proof for the developed implementation is outlined