The Grid File

ACM Transactions on Database Systems - Tập 9 Số 1 - Trang 38-71 - 1984
J. Nievergelt1, Hans Hinterberger1, Kenneth C. Sevcik2
1Institut für Informatik, ETH
2University of Toronto

Tóm tắt

Traditional file structures that provide multikey access to records, for example, inverted files, are extensions of file structures originally designed for single-key access. They manifest various deficiencies in particular for multikey access to highly dynamic files. We study the dynamic aspects of file structures that treat all keys symmetrically, that is, file structures which avoid the distinction between primary and secondary keys. We start from a bitmap approach and treat the problem of file design as one of data compression of a large sparse matrix. This leads to the notions of a grid partition of the search space and of a grid directory , which are the keys to a dynamic file structure called the grid file . This file system adapts gracefully to its contents under insertions and deletions, and thus achieves an upper bound of two disk accesses for single record retrieval; it also handles range queries and partially specified queries efficiently. We discuss in detail the design decisions that led to the grid file, present simulation results of its behavior, and compare it to other multikey access file structures.

Từ khóa


Tài liệu tham khảo

10.1145/320107.320125

10.1145/361002.361007

10.1109/TSE.1979.234200

10.1145/588058.588070

10.1145/362342.362353

10.1145/320083.320092

FINKEL R.A. AND BENTLEY J.L. Quad trees--a data structure for retrieval on composite keys. Acta Inf. 4 {1974) 1-9. FINKEL R.A. AND BENTLEY J.L. Quad trees--a data structure for retrieval on composite keys. Acta Inf. 4 {1974) 1-9.

10.1145/588111.588153

GUETING , H. , AND KRIEGEL , H.P. Multidimensional B-tree : an efficient dynamic file structure for exact match queries. Forschungsbericht Nr. 105, Informatik, Univ. Dortmund , Dortmund , West Germany , 1980 . GUETING, H., AND KRIEGEL, H.P. Multidimensional B-tree: an efficient dynamic file structure for exact match queries. Forschungsbericht Nr. 105, Informatik, Univ. Dortmund, Dortmund, West Germany, 1980.

H{ NRICHS , K. , AND NIEVERGELT , J. The grid file: a data structure designed to support proximity queries on spatial objects . In Proc. Workshop on Graph Theoretic Concepts in Computer Science (Osnabruck , 1983 ). H{NRICHS, K., AND NIEVERGELT, J. The grid file: a data structure designed to support proximity queries on spatial objects. In Proc. Workshop on Graph Theoretic Concepts in Computer Science (Osnabruck, 1983).

H{ NTERBERGER , H. , AND NIEVERGELT , J. Concurrency control in two-level file structures. Working paper , Informatik , ETH Zurich , 1983 . H{NTERBERGER, H., AND NIEVERGELT, J. Concurrency control in two-level file structures. Working paper, Informatik, ETH Zurich, 1983.

J0 SHI , S.M. , SANYAL , S. , BANERJEE , S. , AND SRIKUMAR , S. Using grid files for a relational database management system . Speech and Digital Systems Group , Tata Institute of Fundamental Research, Homi Bhabha Road, Bombay 400 005, India. J0SHI, S.M., SANYAL, S., BANERJEE, S., AND SRIKUMAR, S. Using grid files for a relational database management system. Speech and Digital Systems Group, Tata Institute of Fundamental Research, Homi Bhabha Road, Bombay 400 005, India.

KASHYAP , R.L. , SUBAS , S.K. C., AND YAO , S.B . Analysis of the multiattribute tree database organization . IEEE Trans. Softw. Eng. 2 , 6 ( Nov. 1977 ). KASHYAP, R.L., SUBAS, S.K.C., AND YAO, S.B. Analysis of the multiattribute tree database organization. IEEE Trans. Softw. Eng. 2, 6 (Nov. 1977).

KNUTH , D.E. The Art of Computer Programming. Vo{. 3, Sorting and Searching . Addison- Wesley , Reading, Mass ., 1973 . KNUTH, D.E. The Art of Computer Programming. Vo{. 3, Sorting and Searching. Addison- Wesley, Reading, Mass., 1973.

10.1145/320613.320618

L} TWXN , W. Linear hashing: a new tool for file and table addressing . In Proc. 6th international Conference on Very Large Data Bases , 1980 , pp. 212 - 223 . L}TWXN, W. Linear hashing: a new tool for file and table addressing. In Proc. 6th international Conference on Very Large Data Bases, 1980, pp. 212-223.

10.1016/0306-4379(77)90007-2

10.1145/362790.362794

BARNES , M.C. , COLLENS , D.S. Storing hierarchic database structures in transposed form . Datafair , 1973 . BARNES, M.C., COLLENS, D.S. Storing hierarchic database structures in transposed form. Datafair, 1973.

MERRETT , T.H. Multidimensional paging for efficient database querying . In Proc. ICMOD ( Milano, Italy , June 1978 ), pp. 277 - 289 . MERRETT, T.H. Multidimensional paging for efficient database querying. In Proc. ICMOD (Milano, Italy, June 1978), pp. 277-289.

MERRETT , T.H. , AND OTOO , E.J. Dynamic multipaging: a storage structure for large shared data banks. Rep. SOCS-81-26 , McGill Univ. , 1981 . MERRETT, T.H., AND OTOO, E.J. Dynamic multipaging: a storage structure for large shared data banks. Rep. SOCS-81-26, McGill Univ., 1981.

10.1145/362919.362933

NIEVERGELT , J. Trees as data and file structures . In CAAP '81, Proc. 6th Colloquium on Trees in Algebra and Programming , E. Astesiano and C. Bohm, Eds., Lecture Notes in Computer Science 112, Springer Verlag , 1981 , pp. 35 - 45 . NIEVERGELT, J. Trees as data and file structures. In CAAP '81, Proc. 6th Colloquium on Trees in Algebra and Programming, E. Astesiano and C. Bohm, Eds., Lecture Notes in Computer Science 112, Springer Verlag, 1981, pp. 35-45.

NIEVERGELT , J. , HINTERBERGER , H. , AND SEVCIK , K.C. The grid file: an adaptable, symmetric multikey file structure . In Trends in Information Processing Systems, Proc. 3rd ECI Conference , A. Duijvestijn and P. Lockemann, Eds., Lecture Notes in Computer Science 123, Springer Verlag , 1981 , pp. 236 - 251 . NIEVERGELT, J., HINTERBERGER, H., AND SEVCIK, K.C. The grid file: an adaptable, symmetric multikey file structure. In Trends in Information Processing Systems, Proc. 3rd ECI Conference, A. Duijvestijn and P. Lockemann, Eds., Lecture Notes in Computer Science 123, Springer Verlag, 1981, pp. 236-251.

10.1016/0020-0190(82)90027-8

10.1145/359007.359013

10.1137/0205003

10.1145/582318.582321

10.1145/360827.360831

10.1016/0306-4379(82)90024-2

10.1007/BF01934393

10.1145/942574.807128

Thông tin
Thông tin xuất bản

ACM Transactions on Database Systems

Tập 9 Số 1

38-71

Thông tin tác giả