Wie lagern Sie eine Trie in einer relationalen Datenbank?

Question

Ich habe einen Präfix trie. Was ist das empfohlene Schema diese Struktur in einer relationalen Datenbank zur Darstellung? Ich brauche Teilzeichenanpassung leistungsfähig zu bleiben.

Answer 1

Wie über die materialisierten Pfad entwerfen?

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

Um ein Wort zu speichern, wie "Stackoverflow":

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

Der materialisierte Pfad in dem Baum ist die Präfix Folge von Zeichen selbst. Dies bildet auch den Primärschlüssel. Die Größe der Varchar-Spalte ist die maximale Tiefe der Trie Sie speichern möchten.

Ich kann mich nichts mehr einfach und unkompliziert als das, und es bewahrt effiziente String Speicherung und Suche.

Answer 2

Hat einer Ihrer Einheiten haben eine Beziehung mit einem anderen? Wenn nicht, das heißt, nicht relational, eine Hash-Tabelle mit einer Serialisierung würde es tun.