Quelle est la technique d'indexation des données la plus efficace

10

Comme nous le savons tous, il existe des techniques d'indexation de données, utilisées par des applications d'indexation bien connues, comme Lucene (pour java) ou Lucene.NET (pour .NET), MurMurHash, B + Tree, etc. Pour un No-Sql / Object Base de données orientée (que j'essaie d'écrire / de jouer un peu avec C #), quelle technique proposez-vous?

J'ai lu sur MurMurhash-2 et les commentaires spécialement v3 disent que Murmur est très rapide. Lucene.Net a également de bons commentaires à ce sujet. Mais qu'en est-il de leur empreinte mémoire en général? Existe-t-il une solution efficace qui utilise moins d'encombrement (et bien sûr si plus rapide est préférable) que Lucene ou Murmur? Ou dois-je écrire une structure d'index spéciale pour obtenir les meilleurs résultats?

Si j'essaie d'écrire le mien, existe-t-il une échelle acceptée pour une bonne indexation, quelque chose comme 1% du nœud de données ou 5% du nœud de données? Tout indice utile sera apprécié.

sihirbazzz
la source

Réponses:

10

Je pense que vous avez gâché certaines choses dans votre question. Lucene (je ne sais rien de Lucene, NET, mais je suppose que c'est la même chose) est une bibliothèque utilisée pour analyser, diviser en jetons et stocker des documents afin de pouvoir les interroger et les récupérer plus tard. Lucene a un modèle assez ancien mais efficace, il utilise des arbres inversés pour rechercher et récupérer des documents. Sans plus de détails, tous les documents sont divisés en jetons (termes), et pour chaque terme est conservée une structure de données, qui stocke tous les documents contenant le terme donné. Comme une structure de données pourrait être utilisée, un BTree, une table de hachage et dans les dernières révisions majeures, vous pouvez même brancher vos propres structures de données.

Un BTree (voir la page Wikipedia pour plus de détails), est une sorte de structure de données arborescente, qui convient pour travailler avec de gros morceaux de données et est souvent utilisé pour stocker des structures ordonnées arborescentes sur le disque. Pour les autres arbres en mémoire, les performances sont meilleures.

Le hachage Murmur (voir la page Wikipedia pour plus de détails), est une famille de fonctions de hachage utilisées dans la table de hachage. L'implémentation de la table de hachage n'est pas importante, il peut s'agir d'une implémentation chaînée standard ou d'un schéma d'adressage de hachage ouvert plus avancé. L'idée est que les tables de hachage permettent d'obtenir rapidement une clé, à partir d'un ensemble de clés non ordonné, et peuvent répondre à des tâches telles que: cette clé fait-elle partie de cet ensemble de clés? quelle est la valeur associée à cette clé?

Revenons maintenant à votre problème principal. Vous avez une bibliothèque (Lucene) et pour les structures de données, les deux structures de données sont utilisées dans Lucene. Vous voyez maintenant qu'il n'est pas possible de répondre à votre question en ces termes car ils ne sont pas comparables.

Cependant, en ce qui concerne votre empreinte et vos performances, une partie de la question. Tout d'abord, vous devez savoir quel type d'opérations vous devez mettre en œuvre.

Avez-vous seulement besoin d'obtenir de la valeur pour la clé, ou avez-vous besoin de trouver tous les éléments d'une plage? En d'autres termes, avez-vous besoin d'une commande ou non? Si vous le faites, alors un arbre peut vous aider. Si vous ne le faites pas, une table de hachage, qui est plus rapide, pourrait être utilisée à la place.

Avez-vous beaucoup de données qui ne correspondent pas à la mémoire? Si oui, une solution sur disque aiderait (comme BTree). Si vos données correspondent à la mémoire, utilisez la solution en mémoire la plus rapide et utilisez le disque uniquement comme stockage (avec une structure différente, beaucoup plus simple).

rapaio
la source
Merci beaucoup Rapaio :) Les points que vous m'avez donnés sont très utiles et clarifient quelque chose .. Étant donné que je suis un développeur .NET et curieux en C simple (je commence à apprendre) et une nouvelle ancd rapide, fiable et évolutive bien sûr entièrement contrôlable -à court terme: très excité- techniques..Par conséquent, j'ai besoin d'apprendre beaucoup..Pour apprendre, j'essaie de lire tant de documents mais comme vous pouvez le deviner, je suis à la ligne de départ .. Je ne savais pas que BTree avait des avantages sur le disque (dans le monde .Net, tant d'écrivains l'expliquent comme: Une structure de données hiérarchique comme Linked-List..No More!) Merci encore beaucoup
sihirbazzz
Et si vous me le permettez, jusqu'à ce qu'il y ait une explication / réponse de meilleure qualité que la vôtre, je veux l'accepter comme réponse .. Et BTW, Lucene.NET est une implémentation .NET de Lucene de Java
sihirbazzz