Skip to main content
Log in

Organization and maintenance of large ordered indexes

  • Published:
Acta Informatica Aims and scope Submit manuscript

Summary

Organization and maintenance of an index for a dynamic random access file is considered. It is assumed that the index must be kept on some pseudo random access backup store like a disc or a drum. The index organization described allows retrieval, insertion, and deletion of keys in time proportional to logk I where I is the size of the index and k is a device dependent natural number such that the performance of the scheme becomes near optimal. Storage utilization is at least 50% but generally much higher. The pages of the index are organized in a special datastructure, so-called B-trees. The scheme is analyzed, performance bounds are obtained, and a near optimal k is computed. Experiments have been performed with indexes up to 100000 keys. An index of size 15000 (100000) can be maintained with an average of 9 (at least 4) transactions per second on an IBM 360/44 with a 2311 disc.

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

Access this article

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

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

Instant access to the full article PDF.

Similar content being viewed by others

References

  1. Adelson-Velskii, G. M., Landis, E. M.: An information organization algorithm. DANSSSR, 146, 263–266 (1962).

    Google Scholar 

  2. Foster, C. C.: Information storage and retrieval using AVL trees. Proc. ACM 20th Nat'1. Conf. 192–205 (1965).

  3. Landauer, W. I.: The balanced tree and its utilization in information retrieval. IEEE Trans. on Electronic Computers, Vol. EC-12, No. 6, December 1963.

  4. Sussenguth, E. H., Jr.: The use of tree structures for processing files. Comm. ACM, 6, No. 5, May 1963.

Download references

Author information

Authors and Affiliations

Authors

Rights and permissions

Reprints and permissions

About this article

Cite this article

Bayer, R., McCreight, E.M. Organization and maintenance of large ordered indexes. Acta Informatica 1, 173–189 (1972). https://doi.org/10.1007/BF00288683

Download citation

  • Received:

  • Issue Date:

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

Keywords

Navigation