Búsqueda elástica: ¿Por qué la velocidad de consulta del índice invertido ES es tan rápida?
En el índice matricial "documento-palabra clave" que se muestra en la tabla anterior, si el usuario utiliza un motor de búsqueda para buscar una palabra clave objetivo (como Mars), el motor de búsqueda buscará todas las palabras clave en la biblioteca de índice, es decir, los documentos de Mars se incluyen en web_x_1 y web_x_2, y se muestran al usuario en orden de acuerdo con la puntuación del valor del archivo de la página web en sí (como la cantidad de veces que aparece una palabra clave) y cuál es el el usuario obtiene se muestra en orden. Este es el proceso general de indexación directa.
En esta matriz, todas las páginas web correspondientes a las palabras clave de Mars se encuentran de antemano, e incluso los pesos de los documentos de las páginas web se calculan y clasifican previamente. Cuando el usuario ingresa la palabra clave de Mars, obtendrá inmediatamente los resultados de los comentarios de web_x_2 y web_x_1.
Algunas personas aquí pueden preguntarse si hay demasiadas palabras clave que exceden el número de páginas web, para que la eficiencia no se reduzca. De hecho, la cantidad de vocabulario del lenguaje humano es relativamente limitada y fija, pero la cantidad de páginas web no tiene límite superior. Por ejemplo, el chino tiene 30.000 caracteres chinos y alrededor de 400.000 palabras de vocabulario, pero el número de sitios web chinos es mucho mayor.
Cabe señalar que el número de documentos correspondientes a cada palabra cambia dinámicamente, por lo que el establecimiento y mantenimiento de la tabla invertida es más complicado. Sin embargo, durante la consulta, todos los documentos correspondientes a la palabra clave de la consulta se pueden obtener a la vez, por lo que la tabla invertida es más eficiente.
Para esta tabla, Elasticsearch creará los siguientes índices:
Índice1:nombre
Índice2:color
Índice3:ratio
En este índice, los campos de nombre, color y tarifa se llaman archivos, y los campos del iphone 666 plus, azul y medio se llaman $Term, y los identificadores de todos los productos correspondientes a $Term, Por ejemplo, [1, 3] es la lista de publicaciones.
Cuando el usuario quiere encontrar un producto con Color=blue, puede encontrarlo rápidamente a través de $Term y Posting List en el índice tres. El objetivo es un producto con id 2, y luego puede encontrar el. nombre del producto a través del índice uno.
Lo anterior explica brevemente $Term y la lista de publicaciones, pero en la producción real, Elasticsearch necesita enfrentar cientos de millones de registros de datos, y la cantidad de datos $Term es asombrosa, por lo que a menudo cuesta mucho. Se necesita mucho tiempo para lograrlo y la mayoría de las veces la búsqueda es de múltiples condiciones, lo que requiere búsquedas repetidas muchas veces y la eficiencia aún no es alta.
En este momento, es necesario optimizar la clasificación de $Term, es decir, utilizar la búsqueda binaria para encontrar $Term, que es similar a buscar un diccionario, llamado diccionario $Term.
De manera similar, en el ejemplo anterior, todos los $Terms bajo los tres índices de nombre, color y proporción se ordenan según la posición de la primera letra en el alfabeto inglés de la siguiente manera:
Cuando los usuarios quieren encontrar un producto de alta calidad, pueden encontrarlo rápidamente mediante el método de dicotomía. La complejidad temporal del proceso de búsqueda es log N, lo que mejora enormemente la velocidad de búsqueda. Con respecto al método de búsqueda binaria, no entraré en detalles aquí. Si no lo sabe, sus amigos pueden usar Baidu o hacer clic en el método de búsqueda binaria para obtener más información.
Mucha gente aquí tendrá preguntas, entonces, ¿cuál es la diferencia entre este y el árbol B tradicional? Es necesario introducir otro concepto, el índice $Term.
De hecho, el índice $Term también puede entenderse como una estructura de árbol. La clasificación de primer nivel comienza con la primera letra de $Term. Si hay varios $Terms con la misma primera letra, la clasificación de segundo nivel comienza a partir de esa letra. Si solo hay un $Term que comienza con esa letra, la segunda clasificación no se realizará.
El mismo ejemplo anterior, su índice $Term es como se muestra a continuación:
Hay dos $Terms que comienzan con la letra B en la imagen de arriba, que son azul y negro. entonces necesitamos ordenar la segunda letra, es decir, ordenar la segunda letra. En este momento, encontramos que la segunda letra de los dos $Terms es L, por lo que ordenamos en el tercer nivel. Los resultados de la clasificación del tercer nivel son bla y blu, que corresponden a los dos $Terms, negro y azul. y [1, 3] y 2. La relación correspondiente es como se muestra en la siguiente figura:
Lo que se debe guardar en el índice $Term es la primera parte del campo $Term y la relación de mapeo con el diccionario $Term, lo que reduce la cantidad de información almacenada. Combinado con la tecnología de compresión FST (Refine State Translator), el índice $Term se puede comprimir lo suficientemente pequeño como para almacenarlo en caché en la memoria del servidor. De esta manera, cuando el usuario busca, primero encuentra la relación de mapeo de posición en el diccionario $Term a partir del índice $Term en la memoria, luego encuentra el $Term correspondiente en el disco y luego encuentra la Lista de publicaciones correspondiente, lo que en gran medida Reduce el número de lecturas de disco. Mejora de la eficiencia y la velocidad.
Para conocer la tecnología de compresión FST, consulte este artículo:/blog/2018/12/04/Lucene-FST/. Si eres bueno en inglés, puedes leer este artículo en https://cs.nyu.edu/~mohri/pub/fla.pdf, que tiene una explicación detallada de FST.
Primero entierra un agujero aquí y rellénalo más tarde cuando tengas tiempo.