1970/01/01 by Raymond Bayer, Edward M. McCreight · 3 citations
Computer Science · #Distributed systems and fault tolerance #Algorithms and Data Compression #Advanced Database Systems and Queries
paper · pdf · doi:10.1145/1734663.1734671
openalex publication_date 1970/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/31
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.