lưu Btrees vào một tệp đĩa và đọc nó

Question

Tôi muốn lưu một Btree (không chắc chắn tệp nhị phân) trong tệp đĩa. và sau đó đọc nó vào bộ nhớ. một số lần truyền tải cấp bậc có thể là một cách tốt cho Btree nhị phân. nhưng nếu nó không phải là nhị phân. Tôi xây dựng Btree từ leafnode đến rootnode trong bộ nhớ. Tôi tin rằng tôi phải xác định một số cấu trúc trong tệp đĩa và xuất ra các nút cây. sử dụng một số thẻ phụ để xác định một nút trong tệp? cách truyền tải có thể là vấn đề chính ở đây. Tôi không tìm ra cách tốt để lưu các nút và các con trỏ. và sau đó đọc. xây dựng cây trong bộ nhớ. bất kỳ ý tưởng hay nào ?. cảm ơn rất nhiều.

Answer 1

Nếu bạn thực sự muốn làm điều gì đó tương tự, bạn chỉ có thể gán tại mỗi nút một id và lưu các nút ở định dạng đó:

[giá trị node-id trái nút-id phải nút-id]

và sau đó truy cập vào cây với tìm kiếm rộng đầu tiên.

Khi bạn muốn xây dựng lại cây, tạo ra một bản đồ id-> nút và sau đó đọc ngược file: như vậy, khi bạn đọc một kỷ lục, tạo ra các nút, đăng ký nó vào bản đồ và gán bên trái và nút phải tìm nạp các nút từ bản đồ.

Answer 2

Đối với mỗi nút xác định một số cấu trúc dữ liệu sẽ giữ cho bạn cùng một thông tin mà nút có và thêm vào trường cấu trúc bổ sung sẽ đánh dấu cho bạn bù đắp trong tệp cho con trai tiếp theo. Và làm cho trường trên cùng của cấu trúc đó là kích thước thực, vì bạn không biết bạn đang tìm loại cây nào. Bây giờ bằng cách nhảy qua tập tin bạn sẽ có thể tái tạo lại cây của bạn. Tôi chắc chắn giải pháp của tôi không phải là cuối cùng, nhưng tôi hy vọng nó có thể là điểm tốt cho bạn.

Answer 3

Bạn có thể muốn xem Protocol Buffers. Chúng nhỏ gọn, nhị phân, có thể mở rộng, dễ đọc và viết và có sẵn trong C++, Java và Python (cũng như triển khai của bên thứ ba bằng các ngôn ngữ khác).

Bạn có thể xác định thông báo bộ đệm giao thức cho nút BTree, với bù đắp tệp cho nút con và chỉ cần tuần tự hóa nó thành đĩa theo cách hiển nhiên.

Answer 4

Kỹ thuật thông thường cho B-Trees là đảm bảo rằng kích thước của một nút bằng kích thước khối của đĩa và mmap tệp đĩa. Bạn không chỉ định ngôn ngữ lập trình nào bạn đang làm việc, vì vậy nó có thể đơn giản như một diễn viên trong C, hoặc một cái gì đó phức tạp hơn chẳng hạn như tạo các đối tượng flyweight để bọc lên một java.nio.IntBuffer. Dù bằng cách nào, phần lớn lợi thế của cây B là bạn không phải tải tất cả cùng một lúc, nhưng có thể nhảy xung quanh nó khá hiệu quả.