Organization and Maintenance of Large Ordered Indices

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

About this paperEnglishbeside English

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.

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.

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.