Skip to main content
SpringerLink
Log in

MultidimensionalB-trees: Analysis of dynamic behavior

  • Part I Computer Science
  • Published:
BIT Numerical Mathematics Aims and scope Submit manuscript

Abstract

The MultidimensionalB-tree (MDBT) is a new method for multiple attribute indexing which uses B-trees to maintain the filial sets at each level and imposes an ordering on these filial sets in order to ensure efficient searching for various associative queries. In this paper, we show that the MDBT provides an attractive alternative to other indexing structures when frequent changes to the database occur. We present algorithms for maintaining the MDBT structure when insertions or deletions are posted which also account for some storage reclamation. Procedures for evaluating the average and worst-case times of our algorithms are given, showing that the maintenance of the MDBT structure can be done at a relatively low cost.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. M. Astrahan et al.,System R: Relational approach to database management, ACM Trans. on Database Syst., 1(2), 97–137, (1976).

    Article  Google Scholar 

  2. R. Bayer and C. McCreight,Organization and maintenance of large ordered indexes, Acta Informatica, 1(3), 173–189, (1972).

    Article  Google Scholar 

  3. J. L. Bentley,Multidimensional binary search trees used for associative searching, Comm. of ACM, 18(9), 509–517, (1975).

    Article  Google Scholar 

  4. J. L. Bentley,Multidimensional binary search trees in database applications, IEEE Trans. on Soft. Eng., SE-5(4), 333–340, (1979).

    Google Scholar 

  5. A. F. Cardenas,Evaluation and selection of file organization—a model and system, Comm. of ACM, 16(9), 540–548, (1973).

    Article  Google Scholar 

  6. A. F. Cardenas and J. P. Sagamang,Double-chained tree data base organization—analysis and design strategies, The Computer Journal, 20(1), 15–26, (1977).

    Article  Google Scholar 

  7. J. M. Chang and K. S. Fu,Extended k-d tree database organization: a dynamic multi-attribute clustering method, Proc. Third COMPSAC Conf., Chicago, Nov. 1979, 39–44.

  8. D. Comer,The ubiquitious B-tree, ACM Computing Surveys, 11(2), 121–138, (1979).

    Article  Google Scholar 

  9. R. Fagin, J. Nievergelt, N. Pippenger, H. R. Strong,Extendible hashing—a fast access method for dynamic files, ACM Trans. on Database Systems, 4(3), 315–344, (1979).

    Article  Google Scholar 

  10. V. Gopalakrishna and C. E. Veni Madhavan,Performance evaluation of attribute-based tree organization, ACM Trans. on Database Syst., 5(1), 69–87, (1980).

    Article  Google Scholar 

  11. E. Gudes and S. Tsur,Experiments with B-tree reorganization, Proc. ACM SIGMOD Intern. Conf. on Manag. of Data, Santa Monica, Calif. 200–206, (1980).

  12. R. L. Kashyap, S. K. C. Subas and S. B. Yao,Analysis of the multiple-attribute-tree data-base organization, IEEE Trans. on Soft. Eng., Vol. SE-3(6), 451–466.

  13. D. E. Knuth,The Art of Computer Programming, Vol. 3:Sorting and Searching, Addison-Wesley, Reading, Mass., (1973).

    Google Scholar 

  14. D. T. Lee and C. K. Wong,Quintary tree: A file structure of multidimensional database systems, ACM Trans. on Database Syst., 5(3), 339–353, (1980).

    Article  Google Scholar 

  15. E. Y. Lien, E. L. Taylor, R. J. Driscoll and L. M. Reynolds,Binary search tree complex—towards the implementations, Proc. First Intern. Conf. on Very Large Data Bases, Framingham, Mass., 540–542, (1975).

  16. W. Litwin,Linear hashing: A new tool for file and table addressing, Proc. Sixth Intern. Conf. on Very Large Data Bases, Montreal, (1980).

  17. V. T. Lum,Multi-attribute retrieval with combined indices, Comm. of ACM, 13(11), 660–665 (1970).

    Article  Google Scholar 

  18. A. L. Rosenberg and L. Snyder,Compact B-trees, Proc. ACM-SIGMOD Intern. Conf. on Manag. of Data, Boston, Mass., 43–51, (1972).

  19. P. Scheuermann and M. Ouksel,Multidimensional B-trees for associative searching in database systems, to appear in Information Systems.

  20. B. Shneiderman,Optimum data base reorganization points, Comm. of ACM, 16(6), 362–365, (1973).

    Article  Google Scholar 

  21. B. Shneiderman,Reduced combined indexes for efficient multiple attribute retrieval, Information Systems, 2(4), 149–154, (1977).

    Article  Google Scholar 

  22. H. Wedekind,On the selection of access paths in a data base system, in Data Base Management, J. Klimbie and K. Koffeman (eds.), North-Holland 385–397, (1974).

Download references

Author information

Authors and Affiliations

  1. Department of Electrical Engineering and Computer Science, Northwestern University, 60201, Evanston, Illinois, USA

    Mohamed Ouksel & Peter Scheuermann

Authors
  1. Mohamed Ouksel
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Peter Scheuermann
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Ouksel, M., Scheuermann, P. MultidimensionalB-trees: Analysis of dynamic behavior. BIT 21, 401–418 (1981). https://doi.org/10.1007/BF01932838

Download citation

  • Received:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01932838

Keywords

Search

Navigation