Edward H. Sussenguth
Abstract
In data processing problems, files are frequently used which must both be searched and altered. Binary search techniques are efficient for searching large files, but the associated file organization is not readily adapted to the file alterations. Conversely, a chained file allocation permits elcient alteration but cannot be searched efficiently. A file organized into a tree-like structure is discussed, and it is shown that such a file may both be searched and altered with times proportional to s log, N, where N is the number of file items and s is a parameter of the tree. It is also shown that optimizing the value of s leads to a search time which is only 25 per cent slower than the binary search. The tree organization employs two data chains and may be considered to be a compromise between the organizations for the binary search and the chained file. The relation of the tree organization to multidimensional indexing and to the trie structure is also discussed.
- 1 IVERSON, K. E. A Programming Language. Wiley, New York (1962). Google Scholar
Digital Library
- 2 NEWELL, A. (Ed.). Information Processing Language--V Manual. Prentice Hall, Englewood Cliffs (1961).Google Scholar
- 3 JOHNSON L. R. On operand structure, representation, storage, and search. Research Report RC-603, IBM Corp. (1962).Google Scholar
- 4 HELLERMAN, H. Addressing multidimensional arrays. Comm. ACM 5 (Apr. 1962), 205-207. Google ScholarDigital Library
- 5 FREDKIN, E. Trie memory. Comm. ACM 3 (Sept. I960), 490- 499. Google ScholarDigital Library
- 6 LAMB, S. M., AND JACOBSEN, W. H. A high-speed large-capacity dictionary system. Mech. Trans. 6 (Nov. 1961), 76-107.Google Scholar
Index Terms
- Use of tree structures for processing files
Recommendations
Use of tree structures for processing files
In data processing problems, files are frequently used which must both be searched and altered. Binary search techniques are efficient for searching large files, but the associated file organization is not readily adapted to the file alterations. ...
Large files, small writes, and pNFS
ICS '06: Proceedings of the 20th annual international conference on SupercomputingWorkload characterization studies highlight the prevalence of small and sequential data requests in scientific applications. Parallel file systems excel at large data transfers but sometimes at the expense of small I/O performance. pNFS is an NFSv4.1 ...
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 ...
Comments