Как вы храните 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

Имеет ли какое-либо из ваших сущностей какое-либо отношение к другому? Если нет, то есть не реляционная, хэш-таблица с сериализацией сделает это.