C/C++: Làm thế nào để lưu trữ dữ liệu trong một tập tin trong cây B

Question

Dường như với tôi rằng một cách lưu trữ dữ liệu trong một cây B như một tệp có thể được thực hiện hiệu quả với C bằng cách sử dụng tệp nhị phân với một chuỗi (mảng) các cấu trúc, với mỗi cấu trúc biểu diễn một nút. Do đó, người ta có thể kết nối các nút riêng lẻ với cách tiếp cận sẽ tương tự như việc tạo danh sách được liên kết bằng cách sử dụng các mảng. Nhưng sau đó các vấn đề mà đạo cụ lên sẽ được xóa một nút, như erasing chỉ một vài byte ở giữa trong một tập tin rất lớn là không thể.

Một cách xóa có thể là theo dõi các nút 'trống' cho đến khi đạt ngưỡng ngưỡng và sau đó tạo một tệp khác sẽ loại bỏ các nút trống. Nhưng điều này là tẻ nhạt.

Có cách nào tốt hơn từ quan điểm đơn giản/hiệu quả để xóa hoặc thậm chí là đại diện cho cây B trong tệp không?

TIA, -Sviiya

Answer 1

tôi đã tìm kiếm rất nhanh chóng và đào lên này: http://people.csail.mit.edu/jaffer/WB nguồn C: http://cvs.savannah.gnu.org/viewvc/wb/wb/c/ - có vẻ như để cung cấp B-cây cơ sở dữ liệu phong cách dựa trên đĩa - mặc dù tham gia một cái nhìn tại "xóa .c "nó dường như ngụ ý nếu bạn xóa một nút tất cả mọi thứ xuống từ nó sẽ được đưa ra - nếu đó là hành vi chính xác sau đó nó âm thanh như một cái gì đó có thể giúp đỡ?

Ngoài ra - B-cây thường được sử dụng trong các hệ thống tệp - bạn có thể không xem xét một số mã hệ thống tệp không?

Độ nghiêng của riêng tôi là hệ thống tệp - nếu bạn có một cây B có kích thước cố định, bất cứ khi nào bạn "xóa" nút thay vì tìm cách xóa tham chiếu, chỉ cần đặt giá trị thành bất kỳ giá trị nào trong mã của bạn. Sau đó, có một thread clean-up chạy để kiểm tra xem có ai mở tập tin để đọc hay không và liệu tất cả có chặn các tập tin và dọn dẹp không.

Answer 2

Bạn cũng có thể sử dụng Berkley DB. Nó hoạt động tốt với các chương trình C và thực hiện cây B +.

Answer 3

Để triển khai B-Trees trong một tệp, bạn có thể sử dụng bù đắp tệp thay cho con trỏ. Ngoài ra, bạn có thể triển khai "trình quản lý bộ nhớ tệp" để bạn có thể sử dụng lại các mục đã xóa trong tệp.

Để khôi phục hoàn toàn các khối đã xóa trong tệp B-Tree, bạn sẽ phải tạo lại B-Tree trong một tệp mới. Cũng nên nhớ rằng hầu hết các hệ điều hành không có phương pháp để cắt bớt các tập tin. Một phương pháp di động để cắt ngắn một tập tin là viết một tập tin mới và phá hủy tập tin cũ.

Một đề xuất khác là phân vùng tệp thành phân vùng B-Tree và phân đoạn dữ liệu (mục). Một phân vùng B-Tree sẽ chứa các trang. Các trang lá sẽ chứa bù đắp cho các mục dữ liệu. Phân vùng dữ liệu sẽ là một phần trong tệp chứa các mục dữ liệu. Bạn có thể sẽ tạo ra nhiều hơn một phân vùng và các phân vùng có thể được xen kẽ.

Tôi đã dành nhiều thời gian chơi với một tệp dựa trên B-Tree, cho đến khi tôi từ bỏ và quyết định để cho một chương trình cơ sở dữ liệu (hoặc máy chủ) xử lý dữ liệu cho tôi.