Experiments with B-tree reorganization

ABSTRACT

B-trees are a commonly used data structure for indexed access to files and databases. Among the desirable properties of B-trees is the fact that they are dynamically rebalanced after each insertion and deletion operation and therefore need not be reorganized as other static access structures e.g., ISAM. Despite the fact that B-trees are dynamically balanced we demonstrate that operational conditions exist under which it pays off to explicitly reorganize B-trees. The rationale being that by explicit reorganization we defer the event of root splitting and hence reduce the cost of subsequent retrieval requests which are the dominant operations. We present a reorganization algorithm that allows control over storage utilization and discuss the circumstances under which it should be applied. We present simulation results that support our contention that reorganization is indeed economically feasible and we conclude with some suggestions for further work in this area.

REFERENCES

• 1: Bayer, R. and McCreight E. 'Organization and Maintenance of Large Ordered Indices' Acta Informatica, Vol. 1, No. 3, pp. 173--189, 1972.
• 2: Rudolf Bayer , Karl Unterauer, Prefix B-trees, ACM Transactions on Database Systems (TODS), v.2 n.1, p.11-26, March 1977 [doi>10.1145/320521.320530]
• 3: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 4: Nakamura, T. and Mizoguchi, T. 'An Analysis of the Storage Utilization Factor in Block Split Data Structuring Schemes' Fourth Conference on Very Large Databases.
• 5: Yao, A. 'On Random 2-3 Trees' Acta Informatica, Vol. 9, No. 2, pp. 159--170, 1978.
• 6: Gio C. Wiederhold, Database Design, McGraw-Hill, Inc., New York, NY, 1977
• 7: Krishnan, N. K. 'On the Reorganization of B-Trees' M.Sc. Thesis, Computer Science, The Pennsylvania State University, September 1978.
• 8: Arnold L. Rosenberg , Lawrence Snyder, Compact B-trees, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582102]