Maintaining dense sequential files in a dynamic environment (Extended Abstract)

ABSTRACT

In this article, we study an alternate approach that shifts the records among adjacent pages rather than using overflow pointers when space is needed for inserting a record in a sequential file. We show how to use this method to achieve a worst-case record insertion-deletion complexity of O[(log2N)/(D-d)] page-accesses, in (d-D)-dense files.

REFERENCES

• 1: B. S. Baker and E. G. Coffman, "Insertion and Compaction Algorithms in Sequentially Allocated Storage," submitted for publication.
• 2: W. R. Franklin, "Padded Lists: Set Operations in Expected -&-thgr;(log log N) Time," Inf. Proc. Letters, 9:4 (1979), pp. 161-166.
• 3: A. Itai, A. G. Konheim, and M. Rodeh, "A Spare Table Implementation of Priority Queues," IBM Tech Rep. RC 8550 (#37269), Nov. 1980.
• 4: G. S. Lueker, "A Data Structure for Orthogonal Range Queries," Proc. 19th Annual Symposium on Foundations of Computer Science (October 1978), pp.28-34).
• 5: G. S. Lueker, "A Transformation for Adding Range Restriction Capability to Dynamic Data Structures for Decomposable Searching Problems," Technical Report #129, Department of Information and Computer Science, University of California, Irvine, February 1979.
• 6: G. S. Lueker and D. E. Willard, "A Data Structure for Dynamic Range Queries," submitted for publication.
• 7: Robert C. Melville , David Gries, Sorting and Searching Using Controlled Density Arrays, Cornell University, Ithaca, NY, 1978
• 8: R. Melville and D. Gries, "Controlled Density Sorting," Inf. Proc. Letters, 10:4 (1980), pp. 169-172.
• 9: Gio C. Wiederhold, Database Design, McGraw-Hill, Inc., New York, NY, 1977
• 10: D. E. Willard, Predicate-Oriented Database Search Algorithms, Ph.D. dissertation, Aiken Computation Laboratory, Harvard University, Submitted May 3, 1978; published in Garland Series of 28 "Outstanding Dissertations in Computer Science."
• 11: D. E. Willard, "The Super B-Tree Algorithm," Technical Report TR-03-79, Aiken Computer Laboratory, Harvard University, January 1979.
• 12: D. E. Willard, "Inserting and Deleting Records in Blocked Sequential Files," submitted for publication.
• 13: D. E. Willard, "A Densification Algorithm with Worst-Case Complexity O{(log2N)/(D-d)}," Bell Laboratories, forthcoming report.
• 14: D. E. Willard and G. Lueker, "A Transformation for Adding Range Restriction Capability to Data Structures," submitted for publication. (The results of this paper stem from {5, 10, 11}.)

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.3 File Systems Management
          Subjects: File organization

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Secondary storage

General Terms:
Theory