Search

Binary search trees are an important technique for organizing large files, because they are efficient for both random and sequential access of records, and for modification of a file. Because of this, they have received a great deal of attention in recent years, and their properties are now better understood than those of most other file organization methods. This paper surveys the main results which have been obtained.

This work first discusses the factors that affect file (data base) organization performance, an elusive subject, and then presents a methodology, a model and a programmed system to estimate primarily total storage costs and average access time of several file organizations, given a specific data base, query characterization and device-related specifications. Based on these estimates, an appropriate file structure may be selected for the specific situation. The system is a convenient tool to study file structures and to facilitate as much as possible the process of data base structure design and evaluation.

The type of search programme we can use depends on the way in which the information is stored within the computer. There are two principle techniques for arranging the files of information about your documents—the item file, in which the record is the document, its identity, its title, etc., and all its descriptors; and the inverted file, in which the record is the descriptor followed by the identities of all the documents to which it applies. Generally speaking, an item file is usually held serially, most commonly on magnetic tape, whereas an inverted file is usually held in a random access device. The reasons for this will become clear later when we discuss the programs.

A generalized file structure is provided by which the concepts of keyword, index, record, file, directory, file structure, directory decoding, and record retrieval are defined and from which some of the frequently used file structures such as inverted files, index-sequential files, and multilist files are derived. Two algorithms which retrieve records from the generalized file structure are presented.

The efficient organization of a very large file to facilitate search and retrieval operations is an important but very complex problem. In this paper we consider the case of a large file in which the frequency of use of its component subfiles are known. We develop the organization of the file so that the average number of entries to locate individual items in it by means of binary search is minimized. The algorithm iteratively partitions the file into "saturated" subfiles, and with each successive iteration the average number of entries to locate an item is reduced until no more improvement is possible. Next, we extend the method to solve the realistic problem of designing an optimal memory hierarchy to hold the file in a computer system. The sizes of various memory components and location of various items of the frequency-dependent file are determined so that the average time to locate an item (over the totality of items) in the memory hierarchy is minimized for a given total cost of the memory system. A number of examples are given to elucidate the methods. Also, the characteristics and results of a Fortran implementation of the algorithms on the CDC 6600 are described.

Library records and their utilization are described and the various types of file organization available are examined. The serial file with a series of inverted indexes is preferred to the simple serial file or a threaded list file. It is shown how various records should be stored, according to their utilization, in the available storage devices in order to achieve optimum cost-performance.

A file directory is a listing of information of the files available to the users of the distributed data base in a computer network. Such a directory will enable a user at any node to determine where in a network a specific sharable file exists. One can consider such a directory to be similar to a card catalogue in a public library. Users at each node may offer to list their files in this directory of public files for sharing purposes. A user may interrogate this list to determine its contents or obtain information on where a specific sharable file exists. The nonshared files is assumed to be stored at the computer that is known to the user and therefore is not considered here. We assume each computer has its own local directory which consists of all the sharable files stored in that computer. To search for a file that is not stored in a local computer, the user must consult the file directory.

The design of generalized data translators, particularly in the area of data base translation, has been the subject of much research in recent years. The practical application of this research has been limited and conducted primarily at the university level. This article outlines the research and development of a prototype generalized file translator by Honeywell.The Honeywell file translator is driven by descriptions of the input file, the output file and the file transformation to take place. These descriptions are provided using a straight-forward, data definition language (FDDL), which can easily be used by an applications programmer accustomed to working with a high level language. Techniques are discussed that attack many problems fundamental to a practical implementation of a generalized file translator. These problems include creating a DDL environment with which the user is familiar, and which includes simple data attribute descriptions; providing adequate performance; and supplying error detection and control at translation time.

An approach to determining an appropriate file structure for a given application is presented, by outlining a methodology for comparing some important aspects of data management system performance. The aspect chosen for analysis is the processing time required to evaluate Boolean functions defined on data values contained within a file structure and select elements from the structure satisfying the expression.Two file structures are studied. The structures are each combinations of hierarchical and inverted file organizations, which differ in the use of the pointers contained in the inverted file. In one case they link a value to nodes corresponding to its occurrence in the data hierarchy and in the second they link a value to the entry which contains the node corresponding to an occurrence.Algorithms for processing within each of the structures are discussed. Each algorithm is then modeled, and approximating models developed for simulation of the algorithms.

We consider a mathematical model of an information network of n nodes, some of which contain copies of a given data file. Within this network, every node is able to communicate with every other node over communication links (a process which may entail routing through intermediate nodes). In particular, we are concerned with transactions with the multiply-located file. Such transactions fall into one of two classes: (1) query traffic between a node and the file, and (2) update traffic. An update message is assumed to be transmitted to every copy of the file, whereas a query is communicated only to a single copy.

In Chapter V the two-step retrieval process of Decoding and File search was described, and it was indicated that these two processes were relatively independent. As a further demonstration of this independence Chapter VI presented detailed descriptions of these de- coders with minimal reference to or contingencies upon the data file organization. Only in one case, the randomizer associated with Fig. 33, was there a restriction placed on the file structure design. Thus, the designer is relatively free to select a decoder, based almost entirely upon the criteria outlined in the last chapter. Similarly, the selection of a data file structure is independent of the decoder.

A file structure designed to provide rapid, random access with minimum storage overhead is presented. Storage and retrieval are achieved by direct attribute combination-to-address transformation thereby negating the necessity for large file dictionaries or list-pointer structures. The attribute combination-to-address transformation is conceptually similar to key-to-address transformation techniques, but the transformation is not limited to operations on a single key but operates on the combination of several independent keys (or any subset of the combination) describing an item or request.A storage and retrieval system utilizing the combinatorial file structure is developed. Storage and retrieval results derived from a simulated document library of 4000 items are presented. The new file organization is shown to have marked value with respect to minimum storage overhead and high retrieval speed.

Requirements for the use of very large files in digital computer systems for both scientific and business applications arise in a variety of circumstances. Certain characteristics of these applications tend to determine the type of file most suitable, where the file may contain well in excess of fifty million alphanumeric characters of information. These characteristics, some or all of which will be important in a particular application, include: 1. the upper and lower size limits of the file and the rate of change in total file size, 2. the volume of data which must be entered into and read from the file, either by other components of the mechanized system or by elements external to the mechanized system, 3. the speed with which each such reference must take place, 4. the average amount of data in one record and the variations in this amount, 5. the form of the original data and the desired form of information extracted from the file, 6. the control requirements dictated by particular kinds of files, especially the means of identification of records contained therein, and 7. the likelihood and implications of any unavailability, temporary or permanent, which may occur of information stored in the file.

A determination is made of the optimum ratio of records to file guides to minimize searching time in an ordered two-level file such as a library card catalog. The solution is proportional to the square root of the number of records in the file container (card drawer). When scanning rates for cards and for file guides are equal, the solution is exactly the square root of file size. Simplifying assumptions employed in this determination are discussed. It is asserted that most library card catalogs contain far fewer file guides than would be justified in order to minimize searching time for users.