Bài viết sưu tầm

Tìm kiếm một bản ghi trên tệp chỉ dẫn

       Giả sử cần tìm một bản ghi có khóa là x, có thể có nhiều cách để duyệt trong tệp chỉ dẫn

 Tìm tuần tự

        Duyệt trong tệp chỉ dẫn các cặp (k, d) trong bảng khối chỉ dẫn, so sánh giá trị x với d; gặp cặp đầu tiên (k’, d’), ví dụ khối (k₁, d₁). Trong khối (k₁, d₁) sẽ tìm tuần tự theo tệp chỉ dẫn cho tới khi gặp giá trị k nào đó bằng x thì giá trị d tương ứng là địa chỉ của bộ cần tìm. Nếu không có giá trị k nào trong khối (k₁, d₁) là bằng x, xem như bản ghi không tồn tại.

       Phương pháp tìm  kiếm nhị phân:

       Phương pháp tìm kiếm tuần tự nói chung là chậm, thường có thể sử dụng các phương pháp khác như phương pháp nhị phân (chia đôi), vì tệp chỉ số bao giờ cũng được sắp xếp. Giả sử tệp chỉ số được lưu trữ trên n khối (b₁, …, b_n). Để tìm một bản ghi có khóa x, trước hết chọn khối b[n/2]. So sánh giá trị k thuộc khối b[n/2] và x, nếu k > x thì bộ cần tìm nằm trong các khối b₁, …, b[n/2], ngược lại nó nằm  trong các khối từ b[n/2+1], …, b[n]. Quá trình lặp lại cho đến khi chỉ còn một khối chứa bản ghi xóa x. Trong khối này tiếp tục tìm tuần tự trong các cặp (k,d) như phương pháp tìm tuần tự.

 – Thêm một bản ghi

       Muốn thêm một bản ghi mới có khóa x vào tệp chỉ dẫn, sử dụng thủ tục tìm một bản ghi như trên để xác định khối b_i (i = 1,…, n) sẽ chứa bản đó. Nếu trong khối b_i còn chỗ thì thêm bản ghi này vào khối đó đúng theo thứ tự sắp xếp của khóa. Việc đặt đúng vị trí này đòi hỏi phải chuyển chỗ các bản ghi đứng sau bản ghi có khóa x trong khối b_i. Nếu bản ghi khóa x là bản ghi đầu tiên của khối thì phải sửa lại khóa thành x trong bảng chỉ dẫn khối.

      Nếu việc thêm bản ghi vào khối b_i hết chỗ thì bản ghi cuối cùng của khối b_i sẽ chuyển sang làm bản ghi đầu tiên của khối b_i+1, khi đó phải sửa lại giá trị (k, d) của khối b_i+1  tương ứng. Nếu bản ghi có khóa x là bản ghi cuối cùng, tức là x lớn hơn mọi khóa k trong tệp chỉ dẫn và mọi b_i đều hết chỗ, khi đó thiết lập một khối mới b_i+1, bản ghi này sẽ là bản ghi đầu tiên của khối mới thành lập này.

Xóa một bản ghi

      Quá trình giống như thêm một bản ghi, lưu ý nếu khi xóa một bản ghi tạo nên một khối rỗng, khi đó có thể loại bỏ cả khối đó

 – Sửa một bản ghi

       Sử dụng thủ tục tìm một bản ghi để xác định bản ghi cần sửa

-                  Nếu các trường cần sửa không phải là trường khóa, việc sửa đổi giá trị của bản ghi tiến hành bình thường, giá trị của bản ghi sau khi sửa được ghi lại vị trí cũ.

-                  Nếu các trường cần sửa tham gia khóa, quá trình sửa sẽ là quá trình thêm và xóa một bản ghi.

Chú ý: tệp chỉ dẫn có thể được cấu trúc một cách đơn giản hơn nhiều. Tệp này chỉ gồm hai trường: khóa k, con trỏ d. Mỗi bản ghi của tệp chỉ dẫn tương ứng với mỗi bản ghi của tệp chính.