¿Cómo funcionan los índices MySQL?

Estoy realmente interesado en cómo funcionan los índices MySQL, más específicamente, ¿cómo pueden devolver los datos solicitados sin escanear toda la tabla?

Está fuera de tema, lo sé, pero si hay alguien que pueda explicarme esto en detalle, estaría muy, muy agradecido.

Básicamente, un índice en una tabla funciona como un índice en un libro (de ahí proviene el nombre):

Supongamos que tiene un libro sobre bases de datos y desea encontrar información sobre, por ejemplo, el almacenamiento. Sin un índice (suponiendo que no haya otra ayuda, como una tabla de contenido), tendría que revisar las páginas una por una, hasta encontrar el tema (eso es un full table scan). Por otro lado, un índice tiene una lista de palabras clave, por lo que consultaría el índice y vería que storagese menciona en las páginas 113-120,231 y 354. Luego podría pasar directamente a esas páginas, sin buscar (esa es una búsqueda con un índice, algo más rápido).

Por supuesto, cuán útil será el índice, depende de muchas cosas, algunos ejemplos, usando el símil anterior:

• si tuviera un libro sobre bases de datos e indexara la palabra "base de datos", vería que se menciona en las páginas 1-59,61-290 y 292 a 400. En tal caso, el índice no es de mucha ayuda y podría ser más rápido para recorrer las páginas una por una (en una base de datos, esto es "mala selectividad").
• Para un libro de 10 páginas, no tiene sentido hacer un índice, ya que puede terminar con un libro de 10 páginas con el prefijo de un índice de 5 páginas, lo cual es una tontería: simplemente escanee las 10 páginas y termine con él .
• El índice también debe ser útil: generalmente no tiene sentido indexar, por ejemplo, la frecuencia de la letra "L" por página.

Lo primero que debe saber es que los índices son una forma de evitar escanear la tabla completa para obtener el resultado que está buscando.

Existen diferentes tipos de índices y se implementan en la capa de almacenamiento, por lo que no hay un estándar entre ellos y también dependen del motor de almacenamiento que esté utilizando.

InnoDB y el índice B + Tree

Para InnoDB, el tipo de índice más común es el índice basado en B + Tree, que almacena los elementos en un orden ordenado. Además, no tiene que acceder a la tabla real para obtener los valores indexados, lo que hace que su consulta regrese mucho más rápido.

El "problema" de este tipo de índice es que debe consultar el valor más a la izquierda para usar el índice. Entonces, si su índice tiene dos columnas, digamos apellido y nombre, el orden en que consulta estos campos es muy importante .

Entonces, dada la siguiente tabla:

CREATE TABLE person (
    last_name VARCHAR(50) NOT NULL,
    first_name VARCHAR(50) NOT NULL,
    INDEX (last_name, first_name)
);

Esta consulta aprovecharía el índice:

SELECT last_name, first_name FROM person
WHERE last_name = "John" AND first_name LIKE "J%"

Pero el siguiente no

SELECT last_name, first_name FROM person WHERE first_name = "Constantine"

Porque estás consultando el first_name primero columna y no es la columna más a la izquierda del índice.

Este último ejemplo es aún peor:

SELECT last_name, first_name FROM person WHERE first_name LIKE "%Constantine"

Porque ahora, está comparando la parte más a la derecha del campo más a la derecha en el índice.

El índice hash

Este es un tipo de índice diferente que desafortunadamente solo admite el backend de memoria. Es increíblemente rápido, pero solo es útil para búsquedas completas, lo que significa que no puede usarlo para operaciones como >, <oLIKE .

Dado que solo funciona para el backend de memoria, probablemente no lo use con mucha frecuencia. El caso principal que se me ocurre en este momento es el que crea una tabla temporal en la memoria con un conjunto de resultados de otra selección y realiza muchas otras selecciones en esta tabla temporal utilizando índices hash.

Si tiene un VARCHARcampo grande , puede "emular" el uso de un índice hash cuando usa un B-Tree, creando otra columna y guardando un hash del gran valor en él. Digamos que está almacenando una URL en un campo y los valores son bastante grandes. También puede crear un campo entero llamado url_hashy usar una función hash como CRC32o cualquier otra función hash para hacer hash de la URL al insertarla. Y luego, cuando necesite consultar este valor, puede hacer algo como esto:

SELECT url FROM url_table WHERE url_hash=CRC32("http://gnu.org");

El problema con el ejemplo anterior es que, dado que la CRC32función genera un hash bastante pequeño, terminará con muchas colisiones en los valores hash. Si necesita valores exactos, puede solucionar este problema haciendo lo siguiente:

SELECT url FROM url_table 
WHERE url_hash=CRC32("http://gnu.org") AND url="http://gnu.org";

Todavía vale la pena analizar las cosas, incluso si el número de colisión es alto porque solo realizará la segunda comparación (la cadena) contra los hashes repetidos.

Desafortunadamente, usando esta técnica, aún necesita golpear la tabla para comparar el urlcampo.

Envolver

Algunos hechos que puede considerar cada vez que quiera hablar sobre la optimización:

1. La comparación de enteros es mucho más rápida que la comparación de cadenas. Se puede ilustrar con el ejemplo sobre la emulación del índice hash en InnoDB.

2. Tal vez, agregar pasos adicionales en un proceso lo hace más rápido, no más lento. Se puede ilustrar por el hecho de que puede optimizar un SELECTdividiéndolo en dos pasos, haciendo que el primero almacene valores en una tabla en memoria recién creada y luego ejecute las consultas más pesadas en esta segunda tabla.

MySQL también tiene otros índices, pero creo que el B + Tree uno es el más utilizado y el hash es bueno, pero puede encontrar los otros en la documentación de MySQL .

Le recomiendo que lea el libro "High Performance MySQL", la respuesta anterior se basó definitivamente en su capítulo sobre índices.

Básicamente, un índice es un mapa de todas sus claves que está ordenado en orden. Con una lista en orden, en lugar de verificar cada clave, puede hacer algo como esto:

1: Ir al centro de la lista: ¿es más alto o más bajo de lo que estoy buscando?

2: Si es más alto, vaya al punto medio entre medio e inferior, si es inferior, medio y superior

3: ¿Es más alto o más bajo? Salta al punto medio nuevamente, etc.

Usando esa lógica, puede encontrar un elemento en una lista ordenada en aproximadamente 7 pasos, en lugar de verificar cada elemento.

Obviamente hay complejidades, pero eso te da la idea básica.

Eche un vistazo a este enlace: http://dev.mysql.com/doc/refman/5.0/en/mysql-indexes.html

Cómo funcionan es un tema demasiado amplio para cubrirlo en una publicación SO.

Aquí está una de las mejores explicaciones de índices que he visto. Lamentablemente es para SQL Server y no MySQL. No estoy seguro de cuán similares son los dos ...

Tome en estos videos para obtener más detalles sobre la indexación

Indización simple Puede crear un índice único en una tabla. Un índice único significa que dos filas no pueden tener el mismo valor de índice. Aquí está la sintaxis para crear un índice en una tabla

CREATE UNIQUE INDEX index_name
ON table_name ( column1, column2,...);

Puede usar una o más columnas para crear un índice. Por ejemplo, podemos crear un índice sobre el tutorials_tbluso de tutorial_author.

CREATE UNIQUE INDEX AUTHOR_INDEX
ON tutorials_tbl (tutorial_author)

Puede crear un índice simple en una tabla. Simplemente omita la palabra clave UNIQUE de la consulta para crear un índice simple. El índice simple permite valores duplicados en una tabla.

Si desea indexar los valores en una columna en orden descendente, puede agregar la palabra reservada DESC después del nombre de la columna.

mysql> CREATE UNIQUE INDEX AUTHOR_INDEX
ON tutorials_tbl (tutorial_author DESC)

Quiero agregar mis 2 centavos. Estoy lejos de ser un experto en bases de datos, pero recientemente he leído un poco sobre este tema; suficiente para que trate de darle un ELI5. Entonces, aquí está la explicación de mayo.

Entiendo como tal que un índice es como un mini espejo de su tabla, más o menos como una matriz asociativa. Si lo alimenta con una clave coincidente, puede saltar a esa fila en un "comando".

Pero si no tenía ese índice / matriz, el intérprete de consultas debe usar un bucle for para recorrer todas las filas y verificar una coincidencia (el escaneo de tabla completa).

Tener un índice tiene la "desventaja" del almacenamiento adicional (para ese mini espejo), a cambio de la "ventaja" de buscar contenido más rápido.

Tenga en cuenta que (en dependencia de su motor de base de datos) la creación de claves primarias, externas o únicas también configura automáticamente un índice respectivo. Ese mismo principio es básicamente por qué y cómo funcionan esas teclas.

Agregar alguna representación visual a la lista de respuestas.

MySQL usa una capa adicional de indirección: los registros de índice secundario apuntan a registros de índice primario, y el índice primario en sí contiene las ubicaciones de las filas en el disco. Si cambia un desplazamiento de fila, solo se necesita actualizar el índice primario.

Advertencia: la estructura de datos del disco se ve plana en el diagrama pero en realidad es un árbol B +.

Fuente: enlace

En MySQL InnoDB, hay dos tipos de índice.

1. Clave primaria que se llama índice agrupado. Las palabras clave de índice se almacenan con datos de registro reales en el nodo de hoja del árbol B +.

2. Clave secundaria que es un índice no agrupado. Estos índices solo almacenan las palabras clave de la clave principal junto con sus propias palabras clave de índice en el nodo de hoja del árbol B +. Entonces, al buscar desde un índice secundario, primero encontrará sus palabras clave de índice de clave principal y escaneará el árbol B + de clave principal para encontrar los registros de datos reales. Esto hará que el índice secundario sea más lento en comparación con la búsqueda de índice primario. Sin embargo, si todas las selectcolumnas están en el índice secundario, entonces no es necesario buscar nuevamente el índice primario B + Tree. Esto se llama índice de cobertura.