Hiểu Cây Fusion?

Question

tôi stumbled trên các Wikipedia page cho họ:

Fusion tree

Và tôi đọc lớp lưu file PDF liên kết ở phía dưới, nhưng nó được tay lượn sóng về cấu trúc dữ liệu riêng của mình và đi vào nhiều chi tiết về chức năng sketch(x). Tôi nghĩ rằng một phần của sự nhầm lẫn của tôi là các bài báo đang cố gắng rất chung chung, và tôi muốn một ví dụ cụ thể để hình dung.

Cấu trúc dữ liệu này có phù hợp để lưu trữ dữ liệu dựa trên các phím số nguyên 32 hoặc 64 bit tùy ý không? Nó khác với cây B như thế nào? Có một phần nói rằng về cơ bản nó là một cây B với một hệ số phân nhánh là B = (lg n)^(1/5). Đối với một cây dân cư đầy đủ với các phím 32 bit, B sẽ là 2. Liệu điều này chỉ trở thành một cây nhị phân? Cấu trúc dữ liệu này có dự định sử dụng chuỗi bit dài hơn nhiều như các khóa không?

Googling của tôi không bật lên bất kỳ điều gì hữu ích khủng khiếp, nhưng tôi sẽ hoan nghênh mọi liên kết tốt về chủ đề này. Đây thực sự chỉ là sự tò mò, vì vậy tôi chưa sẵn sàng trả tiền cho các tệp PDF tại số portal.acm.org.

Answer 1

Tôi đã đọc (chỉ cần vượt qua nhanh) giấy tinh và có vẻ thú vị. Nó cũng trả lời hầu hết các câu hỏi của bạn trong trang đầu tiên.

Bạn có thể tải xuống giấy từ here

HTH!

Answer 2

Tôi đã đọc giấy kết hợp. Các ý tưởng khá thông minh, và bằng các thuật ngữ O, anh ta có thể tạo ra một trường hợp để giành chiến thắng.

Không rõ ràng với tôi rằng đó là chiến thắng trong thực tế. Các yếu tố liên tục quan trọng rất nhiều, và các nhà thiết kế chip làm việc thực sự khó khăn để quản lý tài liệu tham khảo địa phương giá rẻ.

Anh ấy phải có B trong b-trees giả của mình khá nhỏ cho các máy thực (B = 5 cho 32 bit, có thể 10 cho 64 bit). Điều đó nhiều con trỏ khá phù hợp trong một dòng bộ nhớ cache. Sau khi chạm vào dòng đầu tiên (mà anh ta không thể tránh) trong vài trăm chu kỳ, bạn có thể thực hiện tìm kiếm tuyến tính thông qua các khóa trong một vài chu kỳ trên mỗi khóa, có nghĩa là việc thực hiện truyền thống B-tree được mã hóa cẩn thận có vẻ như nên vượt qua các cây nhiệt hạch. (Tôi đã xây dựng mã B-tree như vậy để hỗ trợ hệ thống chuyển đổi chương trình của chúng tôi).

Anh ấy xác nhận danh sách ứng dụng, nhưng không có số so sánh.

Có ai có bằng chứng cứng không? (Triển khai và so sánh?)

Answer 3

Ý tưởng đằng sau cây hợp nhất thực sự khá đơn giản. Giả sử bạn có các phím w-bit (nói 64 bit), ý tưởng là nén (tức là phác thảo) mọi khóa 64 liên tiếp vào một mảng 64 phần tử. Hàm vẽ phác thảo đảm bảo ánh xạ thời gian không đổi giữa các khóa gốc và chỉ mục mảng cho một nhóm nhất định. Sau đó tìm kiếm khóa sẽ tìm kiếm nhóm chứa khóa, đó là O (log (n/64)). Như bạn có thể thấy, thách thức chính là chức năng phác thảo.