Quelle structure de données utiliser

Question

J'ai des millions de fichiers dans les lecteurs locaux (ex: c, d, e) de mon système. Maintenant, pour rechercher un fichier, nous pouvons utiliser des outils intégrés de Windows ou des commandes comme "trouver" dans Linux. Si je veux concevoir mon propre programme "find" qui devrait d'abord analyser tous les répertoires et stocker l'information soit dans un fichier ou une base de données. Maintenant, chaque fois que je veux rechercher un fichier, nous devons d'abord charger l'information de la base de données ou du fichier, puis rechercher.

J'ai besoin de suggestions pour décider quelle structure de données utiliser pour stocker la structure de répertoire qui peut ensuite être chargée et interrogée pour un nom de fichier donné.

Puisque la recherche est basée sur le nom de fichier, j'ai pensé à utiliser Hashmap, où la clé sera nom de fichier et la valeur sera le chemin complet. Utiliser Trie rendra la recherche plus lente. Une autre idée consiste à utiliser l'index inversé. Mais je ne sais pas lequel est le meilleur.

Merci.

Answer 1

Une table de hachage serait vraiment bonne pour cela car elle a O (1) pour find (et insert et remove aussi bien). mais le problème est que vous ne pouvez pas utiliser une table de hachage pour faire une "recherche à distance". Une "recherche à distance" serait comme "Trouvez tous les fichiers qui se terminent par l'extension cpp". Si ce n'est pas un problème pour vous, je suggérerais de mettre en place la table de hachage.

Answer 2

Vous ne pouvez pas utiliser une structure basée sur la mémoire (comme une table de hachage normale). Les structures de mémoire sont bonnes pour la recherche, mais vous devez charger tout le jeu de données en mémoire juste pour rechercher un enregistrement. c'est très lent et parfois l'ensemble de données est trop grand pour tenir dans la mémoire.

Je vous suggère d'essayer une structure basée sur disque comme B-Tree ou Hashmap de mémoire externe. Ils sont optimisés pour le disque et vous pouvez rechercher un enregistrement sans charger l'ensemble de données.

Si vous ne souhaitez pas écrire vous-même une structure de recherche sur disque, essayez LevelDB de Google.