¿Cuál es la técnica de indexación de datos más eficiente?

10

Como todos sabemos, hay algunas técnicas de indexación de datos, que utilizan aplicaciones de indexación conocidas, como Lucene (para java) o Lucene.NET (para .NET), MurMurHash, B + Tree, etc. Para un No-Sql / Object Base de datos orientada (que intento escribir / jugar un poco con C #), ¿qué técnica sugieres?

Leí sobre MurMurhash-2 y especialmente los comentarios de v3 dicen que Murmur es muy rápido. También Lucene.Net tiene buenos comentarios al respecto. Pero, ¿qué pasa con sus huellas de memoria en general? ¿Existe alguna solución eficiente que use menos espacio (y, por supuesto, si es preferible más rápido) que Lucene o Murmur? ¿O debería escribir una estructura de índice especial para obtener los mejores resultados?

Si trato de escribir el mío, ¿hay alguna escala aceptada para una buena indexación, algo así como 1% de nodo de datos o 5% de nodo de datos? Cualquier sugerencia útil será apreciada.

sihirbazzz
fuente

Respuestas:

10

Creo que arruinaste algunas cosas en tu pregunta. Lucene (no sé nada sobre Lucene, NET, pero supongo que es lo mismo) es una biblioteca utilizada para analizar, dividir en tokens y almacenar documentos para poder consultarlos y recuperarlos más tarde. Lucene tiene un modelo bastante antiguo pero efectivo, utiliza árboles invertidos para buscar y recuperar documentos. Sin más detalles, todos los documentos se dividen en tokens (términos), y para cada término se mantiene una estructura de datos, que almacena todos los documentos que contienen el término dado. Como una estructura de datos podría usarse un BTree, una tabla hash y en las últimas revisiones importantes, incluso puede conectar sus propias estructuras de datos.

Un BTree (vea la página de Wikipedia para más detalles), es una especie de estructura de datos de árbol, que es apropiada para trabajar con grandes fragmentos de datos y a menudo se usa para almacenar estructuras ordenadas en forma de árbol en el disco. Para la memoria, otros árboles funcionan mejor.

Murmur hash (consulte la página de Wikipedia para obtener más detalles), es una familia de funciones hash utilizadas en la tabla hash. La implementación de la tabla hash no es importante, podría ser una implementación encadenada estándar o un esquema de direccionamiento hash abierto más avanzado. La idea es que las tablas hash le permiten a uno obtener rápidamente una clave, de un conjunto de claves desordenado, y puede responder a tareas como: ¿esta clave es parte de este conjunto de claves? ¿Cuál es el valor asociado con esta clave?

Ahora volvamos a su problema principal. Tiene una biblioteca (Lucene) y para estructuras de datos, ambas estructuras de datos se utilizan en Lucene. Ahora verá que no es posible responder su pregunta en estos términos, ya que no son comparables.

Sin embargo, con respecto a su huella y rendimiento, parte de la pregunta. En primer lugar, debe saber qué tipo de operaciones necesita implementar.

¿Necesita solo obtener valor para la clave, o necesita encontrar todos los elementos en un rango? En otras palabras, ¿necesitas orden o no? Si lo hace, entonces un árbol puede ayudar. Si no lo hace, podría usarse una tabla hash, que es más rápida.

¿Tiene muchos datos que no se ajustan a la memoria? En caso afirmativo, una solución basada en disco ayudaría (como BTree). Si sus datos se ajustan a la memoria, utilice la solución en memoria más rápida y utilice el disco solo como almacenamiento (con una estructura diferente, mucho más simple).

rapaio
fuente
Muchas gracias Rapaio :) Los puntos que me diste son muy útiles y obtienen algo más claro ... Ya que soy un desarrollador de .NET y curioso en C simple (empiezo a aprender) y nuevo, rápido, confiable, escalable ancd por supuesto, totalmente controlable -en un corto plazo: muy excitado- técnicas ... Así que necesito aprender mucho ... Para aprender, trato de leer tantos documentos pero como puedes adivinar estoy en la línea de inicio ... No sabía que BTree tiene ventajas en el disco (en el mundo .Net, muchos escritores lo explican como: Una estructura de datos jerárquica como Linked-List ... ¡No más!) Muchas gracias de nuevo
sihirbazzz
Y si me lo permiten, hasta que haya una explicación / respuesta de mayor calidad que la suya, quiero aceptar esto como respuesta ... Y, por cierto, Lucene.NET es una implementación .NET del Lucene de Java
sihirbazzz