Using multi-bucket data leaves with overflow chains—performance analysis

摘要

Many file organizations consist of an index or a directory, which is used for search purposes, and a set of data leaves in which the data records are stored. In order to decrease the index size so that it can fit into main memory, such file organizations may use multi-bucket leaves (instead of “ordinary” data leaves), resulting, however, in a reduction of the average disk space utilization. This can be prevented by postponing leaf splits, either by performing partial expansions before splitting or by using overflow chains.In this paper we analyze (under random insertions) file organizations that use multi-bucket leaves with overflow chains, and compare them to file organizations that use multi-bucket leaves and perform partial expansions before splitting. The analysis can be used to investigate both the dynamic and asymptotic behaviors.