Efficient algorithms for maintenance of large database indexes

Installing an update in an indexed database of size N takes O(log N) disk accesses, because of a root-leaf path traversal. If the installing of updates is deferred for a while, until a certain number n of them have been collected, substantial savings can be obtained. Two efficient algorithms for performing such grouped updates are presented and analyzed. The conditions on n are derived for which these algorithms perform better than straightforward update installation. A technique called model scaling, which is borrowed from the domain of fluid mechanics, is used to show how small simulations can be used for the accurate modeling of real-life environments. Some experimental results are presented to validate the analysis as well as justify the assumptions made