Cấu trúc dữ liệu được sử dụng để xây dựng hệ thống tệp?

Question

Cấu trúc dữ liệu nào là tốt nhất để sử dụng cho tổ chức tệp? B-Trees có tốt nhất hay có cấu trúc dữ liệu nào khác có thể truy cập nhanh hơn vào các tệp và tổ chức tốt không? Cảm ơn

Answer 1

Tất cả các hệ thống tệp khác nhau, do đó, có một số lượng lớn cấu trúc dữ liệu thực sự được sử dụng trong các hệ thống tệp.

Nhiều hệ thống tệp sử dụng một số loại bit vector (thường được gọi là bitmap) để theo dõi nơi các khối miễn phí nhất định, vì chúng có hiệu suất tuyệt vời để truy vấn xem khối đĩa cụ thể có đang sử dụng hay không 't áp đảo đầy đủ) hỗ trợ tra cứu nhanh chóng hợp lý của các khối miễn phí.

Nhiều cấu trúc thư mục được lưu trữ cũ hơn (ext và ext2) sử dụng danh sách được liên kết đơn giản. Rõ ràng điều này thực sự đủ nhanh đối với hầu hết các ứng dụng, mặc dù một số loại ứng dụng sử dụng nhiều thư mục lớn có hiệu suất đáng chú ý.

Hệ thống tệp XFS nổi tiếng khi sử dụng B+-trees cho mọi thứ, bao gồm cấu trúc thư mục và hệ thống nhật ký của nó. Từ những gì tôi nhớ từ khóa học hệ điều hành trải qua của tôi, triết lý là vì mất quá nhiều thời gian để viết, gỡ lỗi và hiệu suất điều chỉnh việc thực hiện B +-tree, nên sử dụng nó càng nhiều càng tốt.

Hệ thống tệp khác (ext3 và ext4) sử dụng biến thể của cây B được gọi là HTree mà tôi không quen thuộc lắm. Rõ ràng nó sử dụng một số loại lược đồ băm để giữ cho hệ số phân nhánh cao để có rất ít truy cập đĩa được sử dụng.

Tôi đã nghe giai thoại rằng một số hệ điều hành đã thử sử dụng splay trees để lưu trữ cấu trúc thư mục của chúng nhưng gặp sự cố với chúng. Cụ thể, nó ngăn chặn truy cập đa luồng tới cùng một thư mục từ nhiều độc giả (vì trong cây splay, mỗi truy cập định hình lại cây) và gặp phải một trường hợp cạnh cây sẽ thoái hóa thành một danh sách liên kết nếu tất cả các phần tử của cây được truy cập tuần tự. Điều đó nói rằng, tôi không biết đây có phải là một truyền thuyết đô thị hay không, vì những vấn đề này rõ ràng trước khi bất cứ ai cố gắng mã hóa chúng.

Hệ thống FAT32 của Microsoft đã sử dụng một mảng lớn (bảng phân bổ tệp) lưu trữ tệp nào được lưu trữ ở đâu và các phần đĩa nào theo một cách hợp lý trong tệp. Hạn chế chính là bảng phải được thiết lập trước, do đó, cuối cùng đã được giới hạn trên về kích thước của các tập tin có thể được lưu trữ trên đĩa. Tuy nhiên, hệ thống dựa trên mảng khá dễ thực hiện.

Đây không phải là danh sách đầy đủ - Tôi chắc chắn rằng các hệ thống tệp khác sử dụng cấu trúc dữ liệu khác. Tuy nhiên, tôi hy vọng nó sẽ giúp bạn đi đúng hướng.

Hy vọng điều này sẽ hữu ích!