R. Bayer
ABSTRACT
Organization and maintenance of an index for a dynamic random access file is considered. It is assumed that the index must be kept on some pseudo random access backup store like a disc or a drum. The index organization described allows retrieval, insertion, and deletion of keys in time proportional to logk I where I is the size of the index and k is a device dependent natural number such that the performance of the scheme becomes near optimal. Storage utilization is at least 50% but generally much higher. The pages of the index are organized in a special data-structure, so-called B-trees. The scheme is analyzed, performance bounds are obtained, and a near optimal k is computed. Experiments have been performed with indices up to 100,000 keys. An index of size 15,000 (100,000) can be maintained with an average of 9 (at least 4) transactions per second on an IBM 360/44 with a 2311 disc.
- Adelson-Velskii, G. M. and Lndis, E. M. An Information Organization Algorithm. DANSSSR, No. 2, 1962.Google Scholar
- Foster, C. C. Information Storage and Retrieval Using AVL Trees. Proc. ACM 20th Nat'l. Conf. (1965), pp. 192--205. Google ScholarDigital Library
- Gladun, V. P. Storage Organization for Key Search and Recording. Cybernetics, Vol. 1, No. 4, August 1965.Google Scholar
- Landauer, W. I. The Balanced Tree and Its Utilization in Information Retrieval. IEEE Trans. on Electronic Computers, Vol. EC-12, No. 6, December 1963.Google Scholar
- Sussenguth, E. H., Jr. The Use of Tree Structures for Processing Files. Comm. ACM, Vol. 6, No. 5, May 1963. Google ScholarDigital Library
Recommendations
On the encipherment of search trees and random access files
Special issue: papers from the international conference on very large data bases: September 22–24, 1975, Framingham, MAThe securing of information in indexed, random access files by means of privacy transformations must be considered as a problem distinct from that for sequential files. Not only must processing overhead due to encrypting be considered, but also threats ...
On the encipherment of search trees and random access files
The securing of information in indexed, random access files by means of privacy transformations must be considered as a problem distinct from that for sequential files. Not only must processing overhead due to encrypting be considered, but also must ...
Organization and maintenance of large ordered indexes
Organization and maintenance of an index for a dynamic random access file is considered. It is assumed that the index must be kept on some pseudo random access backup store like a disc or a drum. The index organization described allows retrieval, ...
Comments