Organization and Maintenance of Large Ordered Indices

Rudolf Bayer, Edward M. McCreight, 1972, Acta Informatica

About this paper

This paper is under a licence that does not allow it to be reproduced, so what is here is its front matter and a short abstract. Read it at the publisher's page.

Tiếng Việt
English

TỔ CHỨC VÀ DUY TRÌ CÁC CHỈ MỤC LỚN CÓ THỨ TỰ bởi

R. Bayer và

E. McCreight

Báo cáo Khoa học Toán học và Khoa học Thông tin Số 20

Phòng thí nghiệm Khoa học Toán học và Khoa học Thông tin

CÁC PHÒNG THÍ NGHIỆM NGHIÊN CỨU KHOA HỌC BOEING

Tháng 7 năm 1970

TÓM TẮT

Việc tổ chức và duy trì một chỉ mục cho một tệp truy cập ngẫu nhiên động được xem xét. Giả sử rằng chỉ mục phải được lưu giữ trên một thiết bị lưu trữ sao lưu truy cập ngẫu nhiên giả, chẳng hạn như đĩa hoặc trống. Tổ chức chỉ mục được mô tả cho phép truy xuất, chèn và xóa các khóa trong thời gian tỷ lệ với log⁡kI\log_k I trong đó II là kích thước của chỉ mục và kk là một số tự nhiên phụ thuộc vào thiết bị sao cho hiệu năng của lược đồ trở nên gần tối ưu. Việc sử dụng bộ nhớ lưu trữ đạt ít nhất 50% nhưng nói chung cao hơn nhiều. Các trang của chỉ mục được tổ chức trong một cấu trúc dữ liệu đặc biệt, được gọi là cây B. Lược đồ được phân tích, các cận hiệu năng được thu được, và một kk gần tối ưu được tính toán. Các thử nghiệm đã được thực hiện với các chỉ mục lên đến 100,000 khóa. Một chỉ mục có kích thước 15,000 (100,000) có thể được duy trì với trung bình 9 (ít nhất 4) giao dịch mỗi giây trên một IBM 360/44 với một đĩa 2311.

Từ khóa và Cụm từ: Cấu trúc dữ liệu, tệp truy cập ngẫu nhiên, duy trì chỉ mục động, chèn khóa, xóa khóa, truy xuất khóa, phân trang, truy xuất thông tin.

Các hạng mục CR: 3.70, 3.73, 3.74.

  1. Giới thiệu

Trong bài báo này, chúng tôi xem xét vấn đề tổ chức và duy trì một chỉ mục cho một tệp truy cập ngẫu nhiên thay đổi động.

D1-82-0989

ORGANIZATION AND MAINTENANCE OF LARGE ORDERED INDICES by

R. Bayer and

E. McCreight

Mathematical and Information Sciences Report No. 20 Mathematical and Information Sciences Laboratory BOEING SCIENTIFIC RESEARCH LABORATORIES July 1970

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 log⁡kI\log_k I where II is the size of the index and kk 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 kk 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.

Key Words and Phrases: Data structures, random access files, dynamic index maintenance, key insertion, key deletion, key retrieval, paging, information retrieval.

CR Categories: 3.70, 3.73, 3.74.

This section is missing here.

1 Introduction

This section is missing here.

2 **B-Trees**

This section is missing here.

3 The Data Structure and Retrieval Algorithm

This section is missing here.

4 Key Insertion

This section is missing here.

5 Cost of Retrievals and Insertions

This section is missing here.

6 Deletion Process

This section is missing here.

7 Cost of Deletions

This section is missing here.

8 Page Overflow and Storage Utilization

This section is missing here.

9 Maintenance Cost for Index with Insertions and Deletions

This section is missing here.

10 Choice of k

This section is missing here.

11 Experimental Results

References

  1. Adelson-Velskii, G. M. and Landis, E. M. An Information Organization Algorithm. DANSSSR, No. 2, 1962.
  2. Foster, C. C. Information Storage and Retrieval Using AVL Trees. Proc. ACM 20th Nat'l. Conf. (1965), pp. 192-205.
  3. Gladun, V. P. Storage Organization for Key Search and Recording. Cybernetics, Vol. 1, No. 4, August 1965.
  4. Landauer, W. I. The Balanced Tree and Its Utilization in Information Retrieval. IEEE Trans. on Electronic Computers, Vol. EC-12, No. 6, December 1963.
  5. Sussenguth, E. H., Jr. The Use of Tree Structures for Processing Files. Comm. ACM, Vol. 6, No. 5, May 1963.

Read off the page by a vision model reading the page images using olmOCR-2-7B-1025-FP8. Translated into Tiếng Việt by gpt-5, against glossary version 7. Translated from the English.

Read off the page by a vision model reading the page images using olmOCR-2-7B-1025-FP8.