Tổ chức và truy cập tập tin

Tại sao công việc ban đêm của ngân hàng mất cả đêm

• Cho đến thập niên 1980, tài khoản ngân hàng sống trên băng từ. Băng chỉ có thể đọc từ đầu này sang đầu kia, vì vậy các giao dịch trong ngày được sắp xếp vào ban đêm và toàn bộ tập tin chính được đọc từ đầu đến cuối, một lần, để áp dụng chúng.
• Hỏi số dư của một khách hàng giữa buổi chiều và câu trả lời là: cho đến ngày mai. Sự tổ chức của tập tin, không phải tốc độ máy tính, quyết định ngân hàng có thể cung cấp gì.
• Disk mang lại một cách tổ chức khác: tính toán vị trí của bản ghi từ khóa của nó và nhảy đến đó. Đó chính là thứ giúp ATM trả lời trong một giây.
• Bài học này là tổ chức tập tin, hai phương pháp truy cập, và cách chọn từ những gì chương trình thường làm nhất.

Ba cách tổ chức

• Một tập tin tuần tự chứa các bản ghi theo thứ tự chúng được thêm vào, không có sắp xếp. Việc bổ sung nhanh; tìm kiếm đòi hỏi đọc từ đầu. Dùng cho nhật ký và hồ sơ kiểm toán.
• Một tập tin tuần tự chứa các bản ghi được sắp xếp theo một trường khóa. Tìm kiếm nhanh hơn, vì bạn có thể dừng sớm hoặc tìm kiếm nhị phân; chèn chậm, vì các bản ghi sau phải dịch chuyển. Dùng cho tập tin chính được cập nhật theo lô.
• Một ngẫu nhiên, hay tập tin truy cập trực tiếp, chứa mỗi bản ghi tại một vị trí được tính toán từ khóa bản ghi của nó, thường bằng hàm băm. Tra cứu theo khóa rất nhanh; đọc theo thứ tự khóa thì cồng kềnh. Dùng cho bảng tra cứu lớn và tài khoản khách hàng.

Tuần tự: thứ tự đến, không có gì hơn

Tuần tự: cùng các bản ghi, theo thứ tự khóa

Hai phương pháp truy cập

• Truy cập tuần tự đọc từ đầu tập tin đến bản ghi mong muốn. Đây là kiểu truy cập duy nhất mà một tập tin thông thường cho phép, và cũng là cách một tập tin tuần tự được xử lý theo lô.
• Truy cập trực tiếp nhảy ngay vào vị trí đã biết mà không cần đọc những gì nằm trước đó. Đây là cách đọc một tập tin ngẫu nhiên, và một tập tin tuần tự cũng có thể được đọc trực tiếp khi vị trí của khóa đã biết hoặc có chỉ mục.
• Vì vậy sự kết hợp chương trình là: truy cập tuần tự dành cho tập tin thông thường và tập tin tuần tự; truy cập trực tiếp dành cho tập tin tuần tự và tập tin ngẫu nhiên.

Ngẫu nhiên: khóa cho bạn biết nơi cần tìm

Ví dụ minh họa: chọn tổ chức

Các sự đánh đổi, đặt cạnh nhau

• Đáp án đúng luôn được lập luận dựa trên hoạt động chính: chương trình này làm gì nhiều nhất?

Ví dụ minh họa: biện chứng cho sự thay đổi

Khóa phải như thế nào, và tại sao hàm băm lại phá vỡ điều đó

• Truy cập trực tiếp cần một khóa, và khóa đó phải duy nhất đối với một bản ghi. Họ tên không phải là khóa; mã khách hàng thì có.
• Hàm băm biến khóa đó thành địa chỉ bản ghi chỉ qua một phép tính, nên một lần đọc duy nhất đủ để đạt đến bản ghi bất kể tập tin lớn đến đâu.
• Hai khóa khác nhau có thể bị băm về cùng một địa chỉ. Đó là xung đột, và nó không phải lỗi thuật toán: nó là điều không thể tránh khỏi khi số lượng khóa khả dĩ vượt quá số địa chỉ.
• Giải pháp được nêu trong điểm chuẩn là khu vực tràn, hoặc lưu một con trỏ tại địa chỉ đó trỏ đến một chuỗi các bản ghi chia sẻ địa chỉ đó. Do đó, xung đột chỉ tốn thêm một lần đọc chứ không mất bản ghi.
• Vì vậy so sánh trung thực là: hàm băm cung cấp truy cập gần như không đổi cho đến khi tập tin đầy, và hiệu suất giảm sút khi các xung đột tích tụ. Truy cập tuần tự không bao giờ suy giảm nhưng vốn dĩ chưa bao giờ nhanh.

Điểm số dễ mất

Bạn đã nắm vững