Comment stockez-vous un trie dans une base de données relationnelle?

Question

J'ai un préfixe trie. Quel est le schéma recommandé pour représenter cette structure dans une base de données relationnelle? J'ai besoin de la sous-chaîne correspondante pour rester efficace.

Answer 1

Qu'en est-il du design Materialized Path?

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

Pour mémoriser un mot comme « stackoverflow »:

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

Le chemin matérialisé dans l'arbre est la séquence de caractères préfixé lui-même. Cela forme également la clé primaire. La taille de la colonne varchar est la profondeur maximum de trie que vous voulez stocker.

Je ne peux pas penser à quelque chose de plus simple et direct que cela, et il préserve le stockage et la recherche de chaîne efficace.

Answer 2

Est-ce que l'une de vos entités a une relation avec une autre? Sinon, c'est-à-dire non relationnel, une table de hachage avec une sérialisation le ferait.