Dynamic multipaging in even less space

ABSTRACT

We present an improvement to the directory structure of dynamic multipaging which reduces the overall storage requirement from The outstanding advantage of multipaging is that it provides multi-attribute access to a database file using directories of negligible size. The present improvement makes the directory size even more negligible and the addressing algorithm easier.

REFERENCES

• 1: 1. R. Bayer & E. M. McCreight, 1972. Organization and maintenance of large ordered indices. Acta Informatica 1 3, 173-89.
• 2: 2. W. Litwin, 1980. Linear hashing: a new tool for file and table addressing. Proc. VLDB6, 212-23.
• 3: 3. T. H. Merrett, 1978. Multidimensional paging for efficient database querying. Proc. ICMOD '78, Internat. Conf. on Data Base Management Systems, FAST, Milano, Italy (29-30 June, 1978) 277-90.
• 4: T H Merrett, Relational Information Systems, Reston Publishing Co., Reston, VA, 1984
• 5: 5. T. H. Merrett & E. J. Otoo, 1982. Dynamic multipaging: a storage structure for large shared data banks in Peter Scheuermann ed. Improving Database Usability and Responsiveness, Academic Press, 237-55.
• 6: J. Nievergelt , Hans Hinterberger , Kenneth C. Sevcik, The Grid File: An Adaptable, Symmetric Multikey File Structure, ACM Transactions on Database Systems (TODS), v.9 n.1, p.38-71, March 1984 [doi>10.1145/348.318586]
• 7: 7. E. J. Otoo & T. H. Merrett, 1983. A storage scheme for extendible arrays. Computing 21. 1-9.
• 8: Arnold L. Rosenberg, Allocating Storage for Extendible Arrays, Journal of the ACM (JACM), v.21 n.4, p.652-670, Oct. 1974 [doi>10.1145/321850.321861]
• 9: 9. A.L. Rosenberg, 1975. Managing storage for extendible arrays. SLAM Journal of Comp. 4 5, 287-306.
• 10: Arnold L. Rosenberg , Larry J. Stockmeyer, Hashing Schemes for Extendible Arrays, Journal of the ACM (JACM), v.24 n.2, p.199-221, April 1977 [doi>10.1145/322003.322006]
• 11: 11. A.L. Rosenberg & L.J. Stockmeyer, 1976b. Storage schemes for boundedly extendible arrays. Acta Informatica 7 3, 289-303.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Segmentation**

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Allocation/deallocation strategies
      D.4.3 File Systems Management
          Subjects: Directory structures; File organization

  E. Data
  E.1 DATA STRUCTURES
      Subjects: Arrays
  E.5 FILES
      Subjects: Optimization**; Sorting/searching; Organization/structure

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process; Query formulation

General Terms:
Algorithms, Design, Performance