Làm thế nào để bạn lưu trữ một trie trong một cơ sở dữ liệu quan hệ?

Question

Tôi có một tiền tố trie. Lược đồ được đề nghị để biểu diễn cấu trúc này trong một cơ sở dữ liệu quan hệ là gì? Tôi cần kết hợp chuỗi con để duy trì hiệu quả.

Answer 1

Thiết kế Materialized Path như thế nào?

CREATE TABLE trie (
    path VARCHAR(<maxdepth>) PRIMARY KEY, 
    ...other attributes of a tree node... 
); 

Để lưu trữ một từ như "stackoverflow":

INSERT INTO trie (path) VALUES 
    ('s'), ('st'), ('sta'), ('stac'), ('stack'), 
    ('stacko'), ('stackov'), ('stackove'), ('stackover'), 
    ('stackover'), ('stackoverf'), ('stackoverflo'), 
    ('stackoverflow'); 

Đường dẫn cụ thể hóa trong cây là chuỗi tiền tố của các nhân vật chính nó. Điều này cũng tạo thành khóa chính. Kích thước của cột VARCHAR là độ sâu tối đa của Trie bạn muốn lưu trữ.

Tôi không thể nghĩ ra bất cứ điều gì đơn giản và đơn giản hơn thế nữa, đồng thời bảo quản lưu trữ và tìm kiếm chuỗi hiệu quả.

Answer 2

Có tổ chức nào của bạn có mối quan hệ với bất kỳ tổ chức nào khác không? Nếu không, đó là, không quan hệ, một bảng băm với một serialization sẽ làm điều đó.