Performance and Stability Analysis of Multilevel Data Structures with Deferred Reorganization

We develop a methodology for analyzing the performance and stability of a server that maintains a multilevel data structure to service a set of access operations for (key,value) records. A subset of the operations executed by the server (e.g., insert and delete) require the multilevel data structure be reorganized so that the server can execute all subsequent requests efficiently. We study how often the server should carry out data reorganization (i.e., maintenance) to maximize its performance. If the server is frequently idle then there is no need to impose the reorganization overhead on the operation requests. The reorganization overhead may be completely eliminated by utilizing server-idling periods. If the server is frequently busy, then the reorganization overhead can be minimized by performing a complete reorganization only after the server has served a sufficient number of insert/delete operations so that the amortized cost per operation is small. Therefore, the issue of how oft..