Как вы храните Trie в реляционной базе данных?

Question

У меня есть префикс Trie. Какова рекомендуемая схема для представления этой структуры в реляционной базе данных? Мне нужно соответствие подстроки, чтобы оставаться эффективным.

Answer 1

Как насчет Материализованного Пути дизайна?

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 - это максимальная глубина записи, которую вы хотите сохранить.

Я не могу придумать ничего более простого и понятного, чем это, и это сохраняет эффективное хранение и поиск строк.

Answer 2

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