У меня есть префикс trie. Какова рекомендуемая схема для представления этой структуры в реляционной базе данных? Мне нужна подстрока, чтобы оставаться эффективной.
Как вы храните trie в реляционной базе данных?
Ответ 1
Как насчет дизайна Materialized Path?
CREATE TABLE trie (
path VARCHAR(<maxdepth>) PRIMARY KEY,
...other attributes of a tree node...
);
Чтобы сохранить слово типа "stackoverflow":
INSERT INTO trie (path) VALUES
('s'), ('st'), ('sta'), ('stac'), ('stack'),
('stacko'), ('stackov'), ('stackove'), ('stackover'),
('stackover'), ('stackoverf'), ('stackoverflo'),
('stackoverflow');
Материализованный путь в дереве - это префиксная последовательность символов. Это также формирует первичный ключ. Размер столбца varchar - это максимальная глубина trie, которую вы хотите сохранить.
Я не могу придумать ничего более простого и простого, и он сохраняет эффективное хранение и поиск строк.
Ответ 2
Отметьте здесь для некоторой проницательности и некоторых ссылок на пример кода.
EDIT: Не видел, чтобы автор редактировал вопрос о деревьях префикса. Но для деревьев вообще вы все равно можете прочитать эти ссылки.
Ответ 3
Имеет ли какое-либо из ваших сущностей какое-либо отношение к другому? Если нет, то есть не реляционная, хэш-таблица с сериализацией сделает это.