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

Question

Comme nous le savons tous, il y a des techniques d'indexation de données, à l'aide par des applications d'indexation bien connus, comme Lucene (pour Java) ou Lucene.NET (pour .NET), MurMurHash, arbre B + etc. Pour Non- sql / Object Oriented Database (que je tente d'écrire / jouer un peu autour avec C #), la technique que vous suggérez?

Je l'ai lu MurMurhash-2 et dire spécialement v3 commentaires Murmur est très rapide. Aussi Lucene.Net a de bons commentaires à ce sujet. Mais qu'en est-leur mémoire footprints en général? Y at-il une solution efficace qui utilise moins l'empreinte (et bien sûr si rapide est préférable) que Lucene ou Murmur? Ou devrais-je écrire une structure d'index spécial pour obtenir les meilleurs résultats?

Si je tente d'écrire mon propre, puis est-il une échelle acceptée pour une bonne indexation, quelque chose comme 1% des données nœuds, ou 5% des données nœuds? Toute indication utile sera apprécié.

Answer 1

Je pense que vous foiré certaines choses dans votre question. Lucene (je ne sais rien Lucene, NET, mais je suppose est le même) est une bibliothèque utilisée pour analyser, diviser en jetons, et stocker des documents afin de pouvoir les rechercher et les récupérer plus tard. Lucene a un modèle assez ancien mais efficace, il utilise des arbres inversée pour trouver 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 maintenu une structure de données qui stocke tous les documents contenant le terme donné. En tant que structure de données peut être utilisé 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.

A BTree (voir Wikipedia pour plus de détails), est une sorte d'une structure de données d'arbre, qui est approprié pour travailler avec de gros morceaux de données et est souvent utilisé pour le stockage d'arbres comme des structures ordonnées sur le disque. Pour d'autres arbres une meilleure performance en mémoire.

hachage Murmur (voir Wikipedia pour plus de détails), est une famille de fonctions de hachage utilisées dans la table de hachage. La mise en œuvre de la table de hachage est pas important, il pourrait être une implémentation standard enchaînée ou plus avancé hachage ouvert système d'adressage. L'idée est que les tables de hachage permet un rapide pour obtenir une clé, à partir d'un ensemble non ordonné de clés, et peuvent répondre à des tâches telles que: est cette partie clé de ce jeu de clés? qui est la valeur associée à cette clé?

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

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

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

Avez-vous beaucoup de données qui ne correspond pas à la mémoire? Si oui qu'une solution sur disque contribueraient (comme BTree). Si vos données correspondent à la mémoire, que l'utilisation de la solution et utiliser le disque en mémoire la plus rapide seulement en tant que stockage (avec une structure différente, beaucoup plus simple).