B-trees re-examined

ABSTRACT

The B-tree and its variants have, with increasing frequency, been proposed as a basic storage structure for multiuser database applications. Here, three potential problems which must be dealt with in such a structure that do not arise in more traditional static directory structures are indicated. One problem is a possible performance penalty.

REFERENCES

• 1: Bayer, R., and McCreight, E. Organization and maintenance of large ordered indices. Proc. 1970 ACM-SIGFIDET Workshop on Data Description and Access, Houston, Tex., Nov. 1970, pp. 107- 141.
• 2: Held, G.D., Stonebraker, M.R., and Wong, E. INGRES-A relational data base system, Proc. AFIPS 1975 NCC, Vol. 44, AFIPS Press, Montvali, N.J., pp. 409-416.
• 3: Held, G., and Stonebraker, M.R., Storage structures and access methods in the relational data base management system, INGRES. Proc. 1975 ACM-PACIFIC, San Francisco, Calif., April 1975, pp. 26-33.
• 4: Keehn, D., and Lacy, J. VSAM data set design parameters. IBM Syst. J. 13, 3 (1974), 186-213.
• 5: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 6: OS ISAM Logic. CY28-6618, IBM, White Plains, N.Y.
• 7: Dennis M. Ritchie , Ken Thompson, The UNIX time-sharing system, Communications of the ACM, v.17 n.7, p.365-375, July 1974 [doi>10.1145/361011.361061]
• 8: Stonebraker, M.R. The choice of partial inversions and combined indices. Int. J. Compt. and Inform. Sci. (June 1974), 167-188.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL

General Terms:
Design, Management, Performance, Theory

Keywords:
B-trees, directory, dynamic directory, index sequential access method, static directory