Giả sử chúng tôi có hàng nghìn tỷ tập được lưu ở đâu đó. Tên miền cho từng bộ này giống nhau. Nó cũng hữu hạn và rời rạc. Vì vậy, mỗi bộ có thể được lưu trữ dưới dạng một trường bit (ví dụ: 0000100111 ...) có độ dài tương đối ngắn (ví dụ: 1024). Nghĩa là, bit X trong bitfield cho biết liệu mục X (trong số 1024 mục có thể) có được bao gồm trong tập hợp đã cho hay không.Cách nhanh nhất để thực hiện thao tác kiểm tra tập hợp con trên một tập hợp lớn các tập hợp có cùng tên miền
Bây giờ, tôi muốn đưa ra một cấu trúc lưu trữ và một thuật toán để trả lời một cách hiệu quả truy vấn: những gì đặt trong kho dữ liệu đã đặt Y làm tập hợp con. Đặt Y chính nó không có trong kho dữ liệu và được chỉ định tại thời gian chạy. Bây giờ cách đơn giản nhất để giải quyết vấn đề này là AND và bitfield cho Y đặt bằng các trường bit của mỗi tập hợp trong kho dữ liệu từng cái một, chọn những kết quả AND có kết quả khớp với bit của Y.
Làm cách nào để tăng tốc độ này? Có một cấu trúc cây (chỉ mục) hoặc một số thuật toán thông minh mà sẽ cho phép tôi thực hiện truy vấn này mà không cần phải AND và mỗi bitfield của bộ lưu trữ?
Có cơ sở dữ liệu nào đã hỗ trợ các hoạt động đó trên các bộ sưu tập lớn không?
Bạn đang sử dụng loại cơ sở dữ liệu nào? Một định dạng độc quyền? SQL Server? –
Sự lựa chọn của DB sẽ phụ thuộc vào việc nó có hiệu quả hỗ trợ các hoạt động thiết lập đã cho trên các tập humongous hay không. Không có DBS SQL nào sẽ mở rộng đến kích thước được yêu cầu (DBMS DBs sẽ là một lựa chọn không tốt cho vấn đề này). Vì vậy, sự lựa chọn là một DB chuyên ngành hoặc một DB mà tôi sẽ thực hiện bản thân mình. – niktech
Bạn đã tìm thấy một số giải pháp? Thật kỳ lạ là không có cơ sở dữ liệu nổi tiếng cho nhiệm vụ này. – actual