© 1991 by British Computer Society
| ||||||||||||||||||||||||||||||||||||||||||||||||||
An Adaptive Overflow Technique to Defer Splitting in B-trees
Department of Computer Science, Monash University, Australia 3168
Time and space trade-off studies by Rosenberg and Snyder (1981) have shown that the space-optimal B-trees are nearly time-optimal. That means efforts to explore a B-tree variant that enhances the space-efficiency of the tree would be worthwhile. Although the compact B-trees of Rosenberg and Snyder (1981) achieve high space utilisation, they require very expensive reorganisations and hence they are impracticable even for relatively small and reasonably stable databases. In addition the storage utilisation of compact B-trees may deteriorate quickly because of splitting of leaf nodes resulting from insertions. The possibility of attaching overflow nodes to the leaf nodes of B-tree to defer the splitting of nodes was proposed in Ref. 7. This paper extends and formalises the new data structure and analyses its performance both quantitatively and by simulation. The performance analysis shows that the additional cost associated with overflow nodes is minimal and the storage utilisation and retrieval performance of the new data structure are similar to that of the compact B-tree.
Received February 1991.
* Department of Computer Science, Monash University, Australia 3168 (e-mail: srini{at}bruce.cs.monash.edu.au)