A general solution of the n-dimensional B-tree problem

ABSTRACT

We present a generic solution to a problem which lies at the heart of the unpredictable worst-case performance characteristics of a wide class of multi-dimensional index designs: those which employ a recursive partitioning of the data space. We then show how this solution can produce modified designs with fully predictable and controllable worst-case characteristics. In particular, we show how the recursive partitioning of an n-dimensional dataspace can be represented in such a way that the characteristics of the one-dimensional B-tree are preserved in n dimensions, as far as is topologically possible i.e. a representation guaranteeing logarithmic access and update time, while also guaranteeing a one-third minimum occupancy of both data and index nodes.

REFERENCES

• Ben75: Jon Louis Bentley, Multidimensional binary search trees used for associative searching, Communications of the ACM, v.18 n.9, p.509-517, Sept. 1975 [doi>10.1145/361002.361007]
• Ben79: J.L.Bentley. Multidimensional Binary Search Trees in Database Applications. IEEE Trans. on Soft. Eng., Vol. SE-5, No. 4, July 1979.
• BM72: R.Bayer and E.McCreight. Organisation and maintenance of large ordered indexes. Acta lnformatica Vol. 1, No. 3, 1972.
• BU77: Rudolf Bayer , Karl Unterauer, Prefix B-trees, ACM Transactions on Database Systems (TODS), v.2 n.1, p.11-26, March 1977 [doi>10.1145/320521.320530]
• Com79: Douglas Comer, Ubiquitous B-Tree, ACM Computing Surveys (CSUR), v.11 n.2, p.121-137, June 1979 [doi>10.1145/356770.356776]
• Fre87: Michael Freeston, The BANG file: A new kind of grid file, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.260-269, May 27-29, 1987, San Francisco, California, United States
• Fre89a: M. W. Forreston, Advances in the design of the BANG file, 3rd International Conference, FODO 1989 on Foundations of Data Organization and Algorithms, p.322-338, July 1989, Paris, France
• Fre89b: M. W. Freeston, A well-behaved file structure for the storage of spatial objects, Proceedings of the first symposium on Design and implementation of large spatial databases, p.287-300, February 1990, Santa Barbara, California, United States
• Fre94: M.Freeston. A general solution of the ndimensional B-tree problem. ECRC Technical Report No. ECRC-94-40.
• Gut84: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• HSW89: A. Henrich , H. -W. Six , P. Widmayer, The LSD tree: spatial access to multidimensional and non-point objects, Proceedings of the 15th international conference on Very large data bases, p.45-53, July 1989, Amsterdam, The Netherlands
• KSS+90: H. -P. Kriegel , M. Schiwietz , R. Schneider , B. Seeger, Performance comparison of point and spatial access methods, Proceedings of the first symposium on Design and implementation of large spatial databases, p.89-114, February 1990, Santa Barbara, California, United States
• LS89: David B. Lomet , Betty Salzberg, The hB-tree: a multiattribute indexing method with good guaranteed performance, ACM Transactions on Database Systems (TODS), v.15 n.4, p.625-658, Dec. 1990 [doi>10.1145/99935.99949]
• Ore86: Jack A. Orenstein, Spatial query processing in an object-oriented database system, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.326-336, May 28-30, 1986, Washington, D.C., United States
• Rob81: John T. Robinson, The K-D-B-tree: a search structure for large multidimensional dynamic indexes, Proceedings of the 1981 ACM SIGMOD international conference on Management of data, April 29-May 01, 1981, Ann Arbor, Michigan [doi>10.1145/582318.582321]
• Sam89: Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• SK90: Bernhard Seeger , Hans-Peter Kriegel, The buddy tree: an efficient and robust access method for spatial data base, Proceedings of the sixteenth international conference on Very large databases, p.590-601, September 1990, Brisbane, Australia
• SRF87: Timos K. Sellis , Nick Roussopoulos , Christos Faloutsos, The R+-Tree: A Dynamic Index for Multi-Dimensional Objects, Proceedings of the 13th International Conference on Very Large Data Bases, p.507-518, September 01-04, 1987

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods

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: Sorting and searching

General Terms:
Algorithms, Design, Performance