¿Cómo funciona la indexación de bases de datos? [cerrado]

¿Por qué es necesario?

Cuando los datos se almacenan en dispositivos de almacenamiento basados ​​en disco, se almacenan como bloques de datos. Se accede a estos bloques en su totalidad, lo que los convierte en la operación de acceso al disco atómico. Los bloques de disco están estructurados de forma muy parecida a las listas enlazadas; ambos contienen una sección para datos, un puntero a la ubicación del siguiente nodo (o bloque) y no es necesario almacenar ambos de forma contigua.

Debido a que una cantidad de registros solo se pueden ordenar en un campo, podemos afirmar que buscar en un campo que no está ordenado requiere una Búsqueda Lineal que requiere (N+1)/2accesos a bloques (en promedio), donde Nes el número de bloques que la mesa se extiende. Si ese campo no es clave (es decir, no contiene entradas únicas), entonces se debe buscar en todo el espacio de tabla en Nlos accesos de bloque.

Mientras que con un campo ordenado se puede utilizar una Búsqueda Binaria, que tiene log2 Naccesos en bloque. Además, dado que los datos se ordenan según un campo que no es clave, no es necesario buscar valores duplicados en el resto de la tabla, una vez que se encuentra un valor más alto. Por tanto, el aumento del rendimiento es sustancial.

¿Qué es la indexación?

La indexación es una forma de ordenar una cantidad de registros en múltiples campos. La creación de un índice en un campo de una tabla crea otra estructura de datos que contiene el valor del campo y un puntero al registro con el que se relaciona. Luego, esta estructura de índice se ordena, lo que permite realizar búsquedas binarias en ella.

La desventaja de la indexación es que estos índices requieren espacio adicional en el disco, ya que los índices se almacenan juntos en una tabla utilizando el motor MyISAM; este archivo puede alcanzar rápidamente los límites de tamaño del sistema de archivos subyacente si se indexan muchos campos dentro de la misma tabla. .

¿Como funciona?

En primer lugar, describamos un esquema de tabla de base de datos de muestra;

Nombre del campo Tipo de datos Tamaño en disco
id (clave principal) INT sin signo 4 bytes
nombre Char(50) 50 bytes
apellido Char(50) 50 bytes
dirección de correo electrónico Char(100) 100 bytes

Nota : se usó char en lugar de varchar para permitir un tamaño preciso en el valor del disco. Esta base de datos de ejemplo contiene cinco millones de filas y no está indexada. Ahora se analizará el rendimiento de varias consultas. Se trata de una consulta que utiliza la identificación (un campo clave ordenado) y otra que utiliza el nombre (un campo no clasificado sin clave).

Ejemplo 1 : campos ordenados frente a campos no clasificados

Dada nuestra base de datos de muestra de r = 5,000,000registros de un tamaño fijo que proporciona una longitud de registro de R = 204bytes y se almacenan en una tabla utilizando el motor MyISAM que utiliza los B = 1,024bytes de tamaño de bloque predeterminados. El factor de bloqueo de la tabla serían bfr = (B/R) = 1024/204 = 5registros por bloque de disco. El número total de bloques necesarios para sostener la mesa es N = (r/bfr) = 5000000/5 = 1,000,000bloques.

Una búsqueda lineal en el campo id requeriría un promedio de N/2 = 500,000accesos a bloques para encontrar un valor, dado que el campo id es un campo clave. Pero como el campo de identificación también está ordenado, se puede realizar una búsqueda binaria que requiera un promedio de log2 1000000 = 19.93 = 20accesos al bloque. Al instante podemos ver que se trata de una mejora drástica.

Ahora el campo firstName no está ordenado ni es un campo clave, por lo que una búsqueda binaria es imposible, ni los valores son únicos y, por lo tanto, la tabla requerirá una búsqueda hasta el final para N = 1,000,000acceder a un bloque exacto. Es esta situación la que la indexación pretende corregir.

Dado que un registro de índice contiene sólo el campo indexado y un puntero al registro original, es lógico que sea más pequeño que el registro de múltiples campos al que apunta. Por lo tanto, el índice en sí requiere menos bloques de disco que la tabla original, lo que por lo tanto requiere menos accesos a bloques para iterar. El esquema para un índice en el campo Nombre se describe a continuación;

Nombre del campo Tipo de datos Tamaño en disco
nombre Char(50) 50 bytes
(puntero de registro) Especial 4 bytes

Nota : Los punteros en MySQL tienen 2, 3, 4 o 5 bytes de longitud según el tamaño de la tabla.

Ejemplo 2 : indexación

Dada nuestra base de datos de muestra de r = 5,000,000registros con una longitud de registro de índice de R = 54bytes y utilizando el tamaño de bloque predeterminado B = 1,024en bytes. El factor de bloqueo del índice serían bfr = (B/R) = 1024/54 = 18registros por bloque de disco. El número total de bloques necesarios para mantener el índice es N = (r/bfr) = 5000000/18 = 277,778bloques.

Ahora una búsqueda utilizando el campo Nombre puede utilizar el índice para aumentar el rendimiento. Esto permite una búsqueda binaria del índice con un promedio de log2 277778 = 18.08 = 19accesos al bloque. Para encontrar la dirección del registro real, lo que requiere un acceso de bloque adicional para leer, lo que eleva el total de 19 + 1 = 20accesos de bloque, muy lejos de los 1.000.000 de accesos de bloque necesarios para encontrar una coincidencia de nombre en la tabla no indexada.

¿Cuándo debería usarse?

Dado que la creación de un índice requiere espacio adicional en disco (277,778 bloques adicionales respecto al ejemplo anterior, un aumento de ~28%) y que demasiados índices pueden causar problemas derivados de los límites de tamaño de los sistemas de archivos, se debe pensar cuidadosamente para seleccionar el correcto. campos a indexar.

Dado que los índices sólo se utilizan para acelerar la búsqueda de un campo coincidente dentro de los registros, es lógico que indexar campos utilizados sólo para la salida sería simplemente una pérdida de espacio en disco y tiempo de procesamiento al realizar una operación de inserción o eliminación y, por lo tanto, debería ser evitado. También dada la naturaleza de una búsqueda binaria, la cardinalidad o unicidad de los datos es importante. La indexación en un campo con una cardinalidad de 2 dividiría los datos a la mitad, mientras que una cardinalidad de 1000 devolvería aproximadamente 1000 registros. Con una cardinalidad tan baja, la efectividad se reduce a una clasificación lineal y el optimizador de consultas evitará usar el índice si la cardinalidad es inferior al 30% del número de registros, lo que efectivamente hace que el índice sea una pérdida de espacio.

Aug 04 '2008 10:08 Xenph Yan