你如何在一个关系数据库中存储一个trie？ [英] How do you store a trie in a relational database?

问题描述

我有一个前缀trie。在关系数据库中表示此结构的建议模式是什么？我需要子串匹配来保持效率。

解决方案

物化路径设计？

  CREATE TABLE trie （
 path VARCHAR（< maxdepth>）PRIMARY KEY，
 ...树节点的其他属性... 
）; 
  

存储一个单词，如stackoverflow：

  INSERT INTO trie（path）VALUES 
（'s'），（'st'），（'sta'），（'stac'），（' ''），
（'stacko'），（'stackov'），（'stackove'），（'stackover'），
（'stackoverf'），（' '），
（'stackoverflow'）; 
  

树中的物化路径是字符本身的前缀序列。这也是主键。 varchar列的大小是要存储的特里的最大深度。

我不能想到比这更简单直接，它保持有效字符串存储和搜索。

I have a prefix trie. What is the recommended schema for representing this structure in a relational database? I need substring matching to remain efficient.

解决方案

How about the Materialized Path design?

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

To store a word like "stackoverflow":

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

The materialized path in the tree is the prefixed sequence of characters itself. This also forms the primary key. The size of the varchar column is the maximum depth of trie you want to store.

I can't think of anything more simple and straightforward than that, and it preserves efficient string storage and searching.

这篇关于你如何在一个关系数据库中存储一个trie？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！