¿Cómo funcionan los índices MySQL?

402

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.

good_evening
fuente
Esta es una pregunta muy amplia. Si tiene un ejemplo específico de una consulta que no utilizará un índice, y no sabe por qué, puede publicarlo y la gente podría ayudarlo.
Hammerite
SELECT * FROM members WHERE id = '1'- Entonces, ¿por qué con index funciona más rápido? ¿Qué hace ese índice aquí?
good_evening
2
Parece una consulta que solo busca un registro indexado específico (tal vez identificado por la clave primaria). El índice lo hace más rápido porque está almacenado en la memoria, se puede ver la fila del índice correspondiente y contiene un puntero al lugar donde se almacenan los datos reales. Entonces MySQL puede ir a la ubicación exacta en la tabla sin tener que escanear la tabla.
Hammerite
¡Muy bien gracias!
Carreras de ligereza en órbita

Respuestas:

513

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.
Piskvor salió del edificio
fuente
3
Estás explicando qué es, no cómo técnicamente funciona internamente.
Tutu Kumari
@Tutu Kumari: Vea las revisiones de la pregunta; no dude en revisar también la respuesta para que se ajuste a la pregunta actual (tenga en cuenta los diversos motores y tipos de índice; consulte, por ejemplo, la documentación aquí: dev.mysql.com/doc/refman/8.0/en/index-btree-hash.html )
Piskvor salió del edificio
259

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.

clarete
fuente
2
¿Tendrán ventaja las siguientes consultas en el caso anterior? 1. SELECT last_name, first_name FROM person WHERE last_name= "Constantine" 2.SELECT last_name, first_name FROM person WHERE last_name LIKE "%Constantine"
Akshay Taru
1
La primera consulta lo hará, la segunda consulta no lo hará. Use EXPLAIN: dev.mysql.com/doc/refman/5.5/en/explain.html Para indexar una segunda consulta con MySQL, debe usar el ÍNDICE DE FULLTEXT: dev.mysql.com/doc/refman/5.5/en/fulltext- search.html
Emilio Nicolás
55
Te voté porque estabas en 127 y la respuesta número 1 fue en 256. No pude evitar hacer que todo fuera agradable y limpio, binariamente.
pbarney
Esta fue una información nueva para mí "ordenar que consultes estos campos es muy importante". Gracias.
Khatri
1
@pbarney después de tres años están cerca de 256 y 512 respectivamente, ¡eso es lo que yo llamo un aumento binario!
nanocv
43

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.

Joshua
fuente
29
Esto se llama búsqueda binaria.
ddlshack
Gracias, finalmente, una respuesta que explica por qué es más rápido y no solo cómo funciona la base de datos con índices.
Gershon Herczeg
El número real de pasos depende en gran medida de los datos: número de valores únicos y distribución en su rango. 7 es el máximo teórico para 100 valores. Discusión completa sobre cómo calcular el número de pasos aquí stackoverflow.com/questions/10571170/…
Joshua
El índice MySQL más común es un árbol B + que funciona de manera similar a una búsqueda binaria pero no exactamente igual. La complejidad algorítmica es la misma, pero la forma en que busca no lo es. Ver en.wikipedia.org/wiki/B-tree
Matt
4

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 ...

Abe Miessler
fuente
2
Buen articulo. No conozco SQL Server, pero el funcionamiento básico es muy similar. (Metanote: deshabilitar los estilos CSS en el segundo artículo vinculado muestra el contenido)
Piskvor dejó el edificio el
3

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)
shahirnana
fuente
1
¡Bienvenido a Stack Overflow! He notado que todas sus respuestas enlazan con sus propios videos. Tenga en cuenta que la autopromoción abierta no está permitida .
SL Barth - Restablece a Mónica el
Quiere promocionar sus videos. LOL
Ilyas karim
1

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.

WoodrowShigeru
fuente
1

Agregar alguna representación visual a la lista de respuestas. ingrese la descripción de la imagen aquí

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

Anush
fuente
1

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.

sendon1982
fuente