database-design - 如何将 trie 存储在关系数据库中？

Question

我有一个前缀特里。在关系数据库中表示这种结构的推荐模式是什么？我需要子字符串匹配以保持效率。

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 列的大小是要存储的最大 trie 深度。

我想不出比这更简单直接的了，它保留了高效的字符串存储和搜索。

Answer 2

您的任何实体是否与任何其他实体有关系？如果不是，也就是说，不是关系的，带有序列化的哈希表会做到这一点。