On-line reorganization of sparsely-populated B+-trees

ABSTRACT

In this paper, we present an efficient method to do online reorganization of sparsely-populated B⁺-trees. It reorganizes the leaves first, compacting in short operations groups of leaves with the same parent. After compacting, optionally, the new leaves may swap locations or be moved into empty pages so that they are in key order on the disk. After the leaves are reorganized, the method shrinks the tree by making a copy of the upper part of the tree while leaving the leaves in place. A new concurrency method is introduced so that only a minimum number of pages are locked during reorganization. During leaf reorganization, Forward Recovery is used to save all work already done while maintaining consistency after system crashes. A heuristic algorithm is developed to reduce the number of swaps needed during leaf reorganization, so that better concurrency and easier recovery can be achieved. A detailed description of switching from the old B⁺-tree to the new B⁺-tree is described for the first time.

REFERENCES

• BS77: R. Bayer and M Schkolnick. C, oncurrency of operations on B-trees. Aeta Informatica, 9(1):1- 21, 1977.
• GR93: Jim Gray , Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1992
• JS93: Theodore Johnson , Dennis Shasha, B-trees with inserts and deletes: why free-at-empty is better than merge-at-half, Journal of Computer and System Sciences, v.47 n.1, p.45-76, Aug. 1993
• LS92: David Lomet , Betty Salzberg, Access method concurrency with recovery, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.351-360, June 02-05, 1992, San Diego, California, United States
• LT95: David B. Lomet , Mark R. Tuttle, Redo Recovery after System Crashes, Proceedings of the 21th International Conference on Very Large Data Bases, p.457-468, September 11-15, 1995
• MN92: C. Mohan , Inderpal Narang, Algorithms for creating indexes for very large tables without quiescing updates, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.361-370, June 02-05, 1992, San Diego, California, United States
• Moh90: C. Mohan, ARIES/KVL: a key-value locking method for concurrency control of multiaction transactions operating on B-tree indexes, Proceedings of the sixteenth international conference on Very large databases, p.392-405, September 1990, Brisbane, Australia
• OLS92: Edward Omiecinski , Liehuey Lee , Peter Scheuermann, Concurrent File Reorganization for Record Clustering: A Performance Study, Proceedings of the Eighth International Conference on Data Engineering, p.265-272, February 03-07, 1992
• Omi88: Edward Omiecinski, Concurrent Storage Structure Conversion: from B+ Tree to Linear Hash File, Proceedings of the Fourth International Conference on Data Engineering, p.589-596, February 01-05, 1988
• Sal88: Betty Salzberg, File structures: an analytic approach, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• SC92: V. Srinivasan , Michael J. Carey, Performance of On-Line Index Construction Algorithms, Proceedings of the 3rd International Conference on Extending Database Technology: Advances in Database Technology, p.293-309, March 23-27, 1992
• SD92: Betty Salzberg , Allyn Dimock, Principles of Transaction-Based On-Line Reorganization, Proceedings of the 18th International Conference on Very Large Data Bases, p.511-520, August 23-27, 1992
• Smi90: Gary Smith. Online reorganization of keysequenced t~bles and files. Tandem System Review, 6(2):52-59, October 1990. Describe algorithm of Franco Putzolu.
• Wed74: H. Wedekind. On the select,on of access paths zn a data base system, chapter Database Management. North Holland Publishing Company, 1974.
• ZS95: (:hendong Zou and Betty SMzberg. On-Line Reorganization of Sparsely-Populated B+trees. Technical Report NU-CCS-95-18, Northeastern University, College of Computer Science, Boston, MA (USA), 1995.

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL

General Terms:
Algorithms, Theory