David B. Lomet
Abstract
A new way to increase file space in dynamically growing files is introduced in which substantial improvement in file utilization can be achieved. It makes use of partial expansions in which, instead of doubling the space associated with some part of the file, the space grows at a slower rate. Unlike previous versions of partial expansion in which the number of buckets involved in file growth is increased by less than a factor of two, the new method expands file space by increasing bucket size via “elastic buckets.” This permits partial expansions to be used with a wide range of indexed files, including B-trees. The results of using partial expansions are analyzed, and the analysis confirmed by a simulation study. The analysis and simulation demonstrate that the file utilization gains are substantial and that fears of excessive insertion cost resulting from more frequent file growth are unfounded.
- 1 BAYER, R., AND MCCREIGHT, E.M. Organization and maintenance of large ordered indices. Acta Inf. I, 3 (1972), 173-189.Google Scholar
Digital Library
- 2 FAGIN, R., NIEVERGELT, J,, PIPPENGER, N., AND STRONG, H.R. Extendible hashing--A fast access method for dynamic files. ACM Trans. Database Syst. 4, 3 (Sept. 1979), 315-344. Google ScholarDigital Library
- 3 KNUTH, D. The Art of Computer Programming. Vol. 3, Sorting and Searching. Addison-Wesley, Reading, Mass., 1973. Google ScholarDigital Library
- 4 LARSON, P. Linear hashing with partial expansions. In Proceedings of the 6th Conference on Very Large Data Bases (Montreal). 1980, pp. 224-232.Google Scholar
- 5 LITWIN, W. Virtual hashing: A dynamically changing hashing. In Proceedings of the 4th Conference on Very Large Data Bases (Berlin). 1978, pp. 517-523.Google Scholar
- 6 LITWIN, W. Linear hashing: A new tool for file and table addressing. In Proceedings of the 6th Conference on Very Large Data Bases (Montreal). 1980, pp. 212-223.Google Scholar
- 7 LITWIN, W., AND LOMET, D. The bounded disorder access method. In Proceedings of the 2nd Conference on Data Engineering (Los Angeles). 1986, pp. 38-48. Google ScholarDigital Library
- 8 LOMET, D.B. Digital B-trees. In Proceedings of the 7th International Conference on Very Large Data Bases (Cannes). 1981, pp. 333-344.Google Scholar
- 9 LOMET, D.B. Bounded index exponential hashing.ACM Trans. Database Syst. 8, 1 (Mar. 1983), 136-165. Google ScholarDigital Library
- 10 LOMET, D.B. A high performance, universal, key associative access method. In Proceedings of the ACM SIGMOD Conference on Management of Data (San Jose, Calif.). 1983, ACM, New York, pp. 120-133. Google ScholarDigital Library
- 11 LOMET, D.B. A simple bounded disorder file organization with good performance. Tech. Pep. TR-86-13 (submitted for publication), Wang Institute {Sept. 1986).Google Scholar
- 12 MA~tTIN, G. Spiral storage: Incrementally augmentable hash addressed storage. Theory of Comput. Rep. 27, Univ. of Warwick, Coventry. Google ScholarDigital Library
- 13 YAo, A. C. -C. Random 3-2 trees. Acta Inf. 9 (1978), 159-170.Google ScholarDigital Library
Index Terms
- Partial expansions for file organizations with an index
Recommendations
A multiple-file write scheme for improving write performance of small files in Fast File System
Fast File System (FFS) stores files to disk in separate disk writes, each of which incurs a disk positioning (seek + rotation) limiting the write performance for small files. We propose a new scheme called co-writing to accelerate small file writes in ...
The Zebra striped network file system
Zebra is a network file system that increases throughput by striping the file data across multiple servers. Rather than striping each file separately, Zebra forms all the new data from each client into a single stream, which it then stripes using an ...
Comments