Có số lượng các thuật toán bằng cách sử dụng, các Directory có thể được thực hiện. Tuy nhiên, việc lựa chọn một thuật toán triển khai Directory thích hợp có thể ảnh hưởng đáng kể đến hiệu suất của hệ thống.
Các bài viết liên quan:
Các thuật toán thực hiện Directory được phân loại theo cấu trúc dữ liệu mà chúng đang sử dụng. Chủ yếu có hai thuật toán được sử dụng trong những ngày này.
Danh sách tuyến tính
Trong thuật toán này, tất cả các tệp trong một Directory được duy trì dưới dạng danh sách đơn lẻ. Mỗi tệp chứa các con trỏ đến các khối dữ liệu được gán cho nó và tệp tiếp theo trong Directory.
Đặc trưng
- Khi một tệp mới được tạo, toàn bộ danh sách sẽ được kiểm tra xem tên tệp mới có khớp với tên tệp hiện có hay không. Trong trường hợp không tồn tại, tệp có thể được tạo ở đầu hoặc cuối. Do đó, việc tìm kiếm một cái tên duy nhất là một mối quan tâm lớn vì việc duyệt qua toàn bộ danh sách rất mất thời gian.
- Danh sách cần được duyệt qua trong trường hợp mọi thao tác (tạo, xóa, cập nhật, v.v.) trên các tệp do đó hệ thống trở nên kém hiệu quả.
Bảng băm
Để khắc phục những hạn chế của việc triển khai danh sách liên kết đơn lẻ của các Directory, có một cách tiếp cận thay thế đó là bảng băm. Cách tiếp cận này đề xuất sử dụng bảng băm cùng với các danh sách được liên kết.
Một cặp khóa-giá trị cho mỗi tệp trong Directory được tạo và lưu trữ trong bảng băm. Khóa có thể được xác định bằng cách áp dụng hàm băm trên tên tệp trong khi các khóa trỏ đến tệp tương ứng được lưu trữ trong Directory.
Giờ đây, việc tìm kiếm trở nên hiệu quả do hiện tại, toàn bộ danh sách sẽ không được tìm kiếm trên mọi hoạt động. Chỉ các mục nhập trong bảng băm được kiểm tra bằng cách sử dụng khóa và nếu mục nhập được tìm thấy thì tệp tương ứng sẽ được tìm nạp bằng giá trị.
