Performance and stability analysis of multilevel data structures with deferred reorganization

We develop a methodology for analyzing the performance and stability of a s erver that maintains a multilevel data structure to service a set of access operations for (key, value) records. A subset of the operations executed b y the server (e.g., insert and delete) require the multilevel data structur e be reorganized so that the server can execute all subsequent requests eff iciently. We study how often the server should carry out data reorganizatio n (i.e., maintenance) to maximize its performance, if the server is frequen tly idle then there is no need to impose the reorganization overhead on the operation requests. The reorganization overhead may be completely eliminat ed by utilizing server-idling periods. If the server is frequently busy, th en the reorganization overhead can be minimized by performing a complete re organization only after the server has served a sufficient number of insert /delete operations so that the amortized cost per operation is small. There fore, the issue of how often one should perform data reorganization to mini mize the average service time depends not only on the multilevel data struc ture maintained by the server but also on the type and intensity of the sys tem workload. The proposed methodology is exemplified with a two-level sort ed file with deferred maintenance. The performance and stability results ar e compared with those of a single-level binary tree data structure with on- the-fly maintenance. It is shown that deferred maintenance of the two-level sorted file outperforms an-the-fly maintenance of the single-level binary tree in both open and closed systems. Furthermore, deferred maintenance can sustain higher workload intensities without risking system stability.