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.
Keywords
B-treeBackupIndex (typography)Random accessComputer scienceIBMScheme (mathematics)MathematicsAlgorithmDatabaseComputer networkPhysics
Related Publications
k-means++: the advantages of careful seeding
The k-means method is a widely used clustering technique that seeks to minimize the average squared distance between points in the same cluster. Although it offers no accuracy g...
On the Optimality of Single-Carrier Transmission in Large-Scale Antenna Systems
A single carrier transmission scheme is presentedfor the frequency selective multi-user (MU) multiple-input singleoutput(MISO) Gaussian Broadcast Channel (GBC) with a basestatio...
Computer Solutions of the Traveling Salesman Problem
Two algorithms for solving the (symmetric distance) traveling salesman problem have been programmed for a high-speed digital computer. The first produces guaranteed optimal solu...
Fit Indices Versus Test Statistics
Model evaluation is one of the most important aspects of structural equation modeling (SEM). Many model fit indices have been developed. It is not an exaggeration to say that ne...
Simulation-Based Optimization with Stochastic Approximation Using Common Random Numbers
The method of Common Random Numbers is a technique used to reduce the variance of difference estimates in simulation optimization problems. These differences are commonly used t...
Publication Info
- Year
- 1970
- Type
- article
- Pages
- 107-107
- Citations
- 194
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
194
OpenAlex
Cite This
Raymond Bayer,
Edward M. McCreight
(1970).
Organization and maintenance of large ordered indices.
, 107-107.
https://doi.org/10.1145/1734663.1734671
Identifiers
- DOI
- 10.1145/1734663.1734671