Sensitivity problem in dynamic file organization
Yuan Y. Sung · 1987
B-trees are very popular dynamic file structures proposed by Bayer and McCreight. Several variants of the B-tree have been introduced with the goal of improving performance. In this paper, we introduce a sensitivity problem that occurs when a B-tree technique (or a similar data structure, such as a B*-tree) is used. Due to this sensitivity problem, the performance of a B-tree may be significantly degraded when many insertions/deletions happen. We propose a method to avoid such a sensitivity problem. Our method has a further advantage that the three parameters used can be accordingly adjusted to accommodate a highly dynamic file.