database design - software - ¿Cómo se almacena un trie en una base de datos relacional?

lucidchart generate sql

Question

Tengo un prefijo trie. ¿Cuál es el esquema recomendado para representar esta estructura en una base de datos relacional? Necesito la coincidencia de subcadenas para seguir siendo eficiente.

Answer 1

¿Alguna de tus entidades tiene una relación con alguna otra? Si no, es decir, no relacional, una tabla hash con una serialización lo haría.

Answer 2

¿Qué tal el diseño de ruta materializada ?

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

Para almacenar una palabra como "":

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

La ruta materializada en el árbol es la secuencia de caracteres prefijada. Esto también forma la clave principal. El tamaño de la columna varchar es la profundidad máxima de trie que desea almacenar.

No puedo pensar en nada más simple y sencillo que eso, y preserva el almacenamiento y la búsqueda eficiente de cadenas.

Answer 3

Consulte aquí para obtener información y algunos enlaces al código de muestra.

EDITAR: No vi que el autor editó la pregunta sobre los árboles de prefijo . Pero para los árboles en general, todavía puede leer esos enlaces.