Al fin luego de tanto luchar hemos dado con la respuesta de esta pregunta que algunos usuarios de nuestro sitio web han tenido. Si quieres compartir algún detalle puedes aportar tu comentario.
Solución:
¿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 la misma forma que 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 al hecho de que varios registros solo se pueden ordenar en un campo, podemos afirmar que la búsqueda en un campo que no está ordenado requiere una búsqueda lineal que requiere N/2 bloquear accesos (en promedio), donde N es el número de bloques que abarca la tabla. Si ese campo no eskey campo (es decir, no contiene entradas únicas), entonces se debe buscar en todo el espacio de tabla en N Bloquear accesos.
Mientras que con un campo ordenado, se puede utilizar una búsqueda binaria, que tiene log2 N Bloquear accesos. Además, dado que los datos se ordenan según unkey , 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 de rendimiento es sustancial.
¿Qué es la indexación?
La indexación es una forma de ordenar varios registros en varios campos. La creación de un índice en un campo en una tabla crea otra estructura de datos que contiene el valor del campo y un puntero al registro con el que se relaciona. A continuación, 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 usando 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;
Field name Data type Size on disk id (Primary key) Unsigned INT 4 bytes firstName Char(50) 50 bytes lastName Char(50) 50 bytes emailAddress Char(100) 100 bytes
Nota: char se usó en lugar de varchar para permitir un tamaño exacto en el valor del disco. Esta base de datos de muestra contiene cinco millones de filas y no está indexada. Ahora se analizará el rendimiento de varias consultas. Estas son una consulta que utiliza el identificación (un ordenado key campo) y uno usando el primer nombre (un nokey campo sin clasificar).
Ejemplo 1 – campos ordenados vs no ordenados
Dada nuestra base de datos de muestra de r = 5,000,000 registros de un tamaño fijo que dan una longitud de registro de R = 204 bytes y se almacenan en una tabla usando el motor MyISAM que usa el tamaño de bloque predeterminado B = 1,024 bytes. El factor de bloqueo de la mesa sería bfr = (B/R) = 1024/204 = 5 registros por bloque de disco. El número total de bloques necesarios para sostener la mesa es N = (r/bfr) = 5000000/5 = 1,000,000 bloques.
Una búsqueda lineal en el campo id requeriría un promedio de N/2 = 500,000 bloquear accesos para encontrar un valor, dado que el campo id es un key campo. Pero dado que el campo id también está ordenado, se puede realizar una búsqueda binaria que requiera un promedio de log2 1000000 = 19.93 = 20 Bloquear accesos. Al instante podemos ver que se trata de una mejora drástica.
Ahora el primer nombre el campo no está ordenado ni key campo, por lo que una búsqueda binaria es imposible, ni los valores son únicos, y por lo tanto, la tabla requerirá buscar hasta el final para un exacto N = 1,000,000 Bloquear accesos. Es esta situación la que la indexación pretende corregir.
Dado que un registro de índice contiene solo 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 de un índice en el primer nombre el campo se describe a continuación;
Field name Data type Size on disk firstName Char(50) 50 bytes (record pointer) Special 4 bytes
Nota: Los punteros en MySQL tienen 2, 3, 4 o 5 bytes de longitud dependiendo del tamaño de la tabla.
Ejemplo 2 – indexación
Dada nuestra base de datos de muestra de r = 5,000,000 registros con una longitud de registro de índice de R = 54 bytes y usando el tamaño de bloque predeterminado B = 1,024 bytes. El factor de bloqueo del índice sería bfr = (B/R) = 1024/54 = 18 registros por bloque de disco. El número total de bloques necesarios para contener el índice es N = (r/bfr) = 5000000/18 = 277,778 bloques.
Ahora una búsqueda usando el primer nombre El campo puede utilizar el índice para aumentar el rendimiento. Esto permite una búsqueda binaria del índice con un promedio de log2 277778 = 18.08 = 19 Bloquear accesos. Para encontrar la dirección del registro real, que requiere un acceso de bloque adicional para leer, llevando el total a 19 + 1 = 20 accesos de bloque, muy lejos de los 1,000,000 accesos de bloque requeridos para encontrar un primer nombre coincidir en la tabla no indexada.
¿Cuándo debería usarse?
Dado que la creación de un índice requiere espacio en disco adicional (277,778 bloques extra del ejemplo anterior, un aumento de ~ 28%), y que demasiados índices pueden causar problemas derivados de los límites de tamaño del sistema de archivos, se debe pensar cuidadosamente para seleccionar el correcto campos para indexar.
Dado que los índices solo se usan para acelerar la búsqueda de un campo coincidente dentro de los registros, es lógico pensar que los campos de indexación usados solo 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 1,000 devolvería aproximadamente 1,000 registros. Con una cardinalidad tan baja, la eficacia se reduce a una ordenación lineal y el optimizador de consultas evitará el uso del índice si la cardinalidad es inferior al 30% del número de registro, lo que hace que el índice sea una pérdida de espacio.
Ejemplo clásico “Índice en libros”
Considere un “Libro” de 1000 páginas, dividido por 10 capítulos, cada sección con 100 páginas.
Simple, ¿eh?
Ahora, imagina que quieres encontrar un Capítulo en particular que contenga una palabra “Alquimista“. Sin una página de índice, no tiene otra opción que escanear todo el libro / capítulos, es decir, 1000 páginas.
Esta analogía se conoce como “Escaneo de tabla completa” en el mundo de las bases de datos.
Pero con una página de índice, ¡sabes a dónde ir! Y más, para buscar cualquier Capítulo en particular que sea importante, solo necesita revisar la página de índice, una y otra vez, cada vez. Después de encontrar el índice coincidente, puede saltar de manera eficiente a ese capítulo omitiendo el resto.
Pero luego, además de las 1000 páginas reales, necesitará otras ~ 10 páginas para mostrar los índices, es decir, un total de 1010 páginas.
Por lo tanto, el índice es una sección separada que almacena los valores de la columna indexada + el puntero a la fila indexada en un orden ordenado para búsquedas eficientes.
Las cosas son sencillas en las escuelas, ¿no? :PAG
Un índice es solo una estructura de datos que agiliza la búsqueda de una columna específica en una base de datos. Esta estructura suele ser un árbol b o una tabla hash, pero puede ser cualquier otra estructura lógica.