This page contains the table of contents for G. H. Sockut and B. R. Iyer, “Online Reorganization of Databases,” Computing Surveys, ACM, 41, 3, Article 14, July 2009, 136 pages.

SECTION	PAGE
1 INTRODUCTION	2
1.1 Reorganization in General	2
1.2 Overview of this Article	4
2 REQUIREMENTS FOR ONLINE REORGANIZATION	5
2.1 Applications that Require Online Reorganization	5
2.2 Required Characteristics of Strategies	6
3 ISSUES IN ONLINE REORGANIZATION	7
3.1 Use of Partitions	7
3.2 The Process that Reorganizes	8
3.2.1 Approaches	8
3.2.2 Considerations for Maintenance	9
3.3 Reorganization by Copying	10
3.3.1 Techniques for Reorganization by Copying	12
3.3.2 Allowance of Updates During Backup	13
3.3.3 Fuzzy Reorganization (A Strategy that Allows Updates During Reorganization)	15
3.3.4 Transitions between Accessing Old and New Copies	20
3.4 Use of Differential Files	21
3.5 References to Data that Has Moved	23
3.5.1 Use of Mapping Tables	23
3.5.2 References in Indexes for Reorganization in Place	25
3.5.3 References in the Log for Fuzzy Reorganization	27
3.5.4 References in Data	29
3.5.5 References in Users' Activities for Reorganization in Place	30
3.6 General Issues in Performance	32
3.6.1 Background	32
3.6.2 Trade-Offs between Users and Reorganization	33
3.6.3 Scheduling of Online Reorganization	35
3.7 Activation of Maintenance	35
3.7.1 Activation of Offline Maintenance	36
3.7.2 Considerations for Activation of Online Maintenance	38
3.7.3 Policies for Activation of Online Maintenance	40
4 STRATEGIES FOR ONLINE MAINTENANCE	43
4.1 Restoration of Clustering	43
4.1.1 Incremental Restoration in Place During Users' Activities	43
4.1.2 Restoration in Place via a Reorganizer	47
4.1.3 Restoration by Copying via a Reorganizer	53
4.2 Reorganization of an Index	55
4.2.1 Background	55
4.2.2 Reorganization in Place	56
4.2.3 Reorganization by Copying	59
4.2.4 Merging of Indexes	60
4.3 Rebalancing of Parallel or Distributed Data	61
4.3.1 Choice of Data to Migrate	62
4.3.2 Growth in the Network	70
4.3.3 Additional Topics	74
4.4 Garbage Collection for Persistent Storage	78
4.4.1 Garbage Collection in Place for Volatile Storage	80
4.4.2 Online Nonpartitioned Garbage Collection in Place for Persistent Storage	82
4.4.3 Online Partitioned Garbage Collection in Place for Persistent Storage	85
4.4.4 Garbage Collection by Copying for Volatile Storage	86
4.4.5 Online Nonpartitioned Garbage Collection by Copying for Persistent Storage	88
4.4.6 Online Partitioned Garbage Collection by Copying for Persistent Storage	89
4.4.7 Comparison of Performance of Strategies for Garbage Collection	91
4.4.8 Comparison of Performance of Policies to Choose a Partition	93
4.5 Cleaning (Reclamation of Space) in a Log-Structured File System	95
5 STRATEGIES FOR ONLINE PHYSICAL REDEFINITION	103
5.1 Construction of Indexes	103
5.2 Conversion Between B+-Trees and Linear Hash Files	109
5.3 Redefinition of Partitions	111
6 STRATEGIES FOR ONLINE LOGICAL REDEFINITION	111
6.1 Interpretation and Incremental Reorganization during Users' Activities	112
6.2 Use of a Reorganizer	114
6.3 Additional Topics	117
7 SUMMARY	118
8 GLOSSARY	118
ACKNOWLEDGEMENTS	120
REFERENCES	120