ORGANIZATION AND MAINTENANCE OF LARGE ORDERED INDICES

Abstract

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 data-structure, so-called B-trees. The scheme is analyzed, performance bounds are obtained, and a near optimal k is computed. Experiments have been performed with indices up to 100,000 keys. An index of size 15,000 (100,000) can be maintained with an average of 9 (at least 4) transactions per second on an IBM 360/44 with a 2311 disc.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 01, 1970
Accession Number
AD0712079

Entities

People

  • E. Mccreight
  • R. Bayer

Organizations

  • Boeing

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Computer Programming
  • Computers
  • Computing-Related Activities
  • Core Storage
  • Data Rate
  • Data Storage Systems
  • Information Retrieval
  • Information Science
  • Information Transfer
  • Maintenance
  • Maintenance Costs
  • Scientific Research
  • Sequences
  • Splitting
  • Trees (Data Structures)

Readers

  • Computer Science/Computer Engineering/Data Science/Digital Signal Processing.
  • Parallel and Distributed Computing.
  • Statistical inference.