Use of tree structures for processing files

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.

REFERENCES

• 1: Kenneth E. Iverson, A Programming Language., John Wiley & Sons, 1962
• 2: NEWELL, A. (Ed.). Information Processing Language--V Manual. Prentice Hall, Englewood Cliffs (1961).
• 3: JOHNSON L. R. On operand structure, representation, storage, and search. Research Report RC-603, IBM Corp. (1962).
• 4: H. Hellerman, Addressing multidimensional arrays, Communications of the ACM, v.5 n.4, p.205-207, April 1962 [doi>10.1145/366920.366943]
• 5: Edward Fredkin, Trie memory, Communications of the ACM, v.3 n.9, p.490-499, September 1960 [doi>10.1145/367390.367400]
• 6: LAMB, S. M., AND JACOBSEN, W. H. A high-speed large-capacity dictionary system. Mech. Trans. 6 (Nov. 1961), 76-107.