database-designschemarelationaltrie

How do you store a trie in a relational database?

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.

Solution

  • 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.