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

Dado que la indexación es tan importante a medida que su conjunto de datos aumenta de tamaño, ¿alguien puede explicar cómo funciona la indexación en un nivel independiente de la base de datos?

Para obtener información sobre las consultas para indexar un campo, consulte Cómo indexar una columna de base de datos .

¿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 manera muy similar a las listas enlazadas; ambos contienen una sección para datos, un puntero a la ubicación del siguiente nodo (o bloque), y ambos no necesitan almacenarse de manera contigua.

Debido al hecho de que una cantidad de registros solo se puede 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/2accesos de bloque (en promedio), donde Nes la cantidad de bloques que La mesa se extiende. Si ese campo es un campo sin clave (es decir, no contiene entradas únicas), se debe buscar en todo el espacio de tabla en los Naccesos de bloque.

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

¿Qué es la indexación?

La indexación es una forma de ordenar una serie de registros en múltiples campos. Crear 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. Esta estructura de índice se ordena, permitiendo que se realicen 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;

Nombre del campo Tipo de datos Tamaño en el disco
id (clave principal) INT sin signo 4 bytes
firstName Char (50) 50 bytes
lastName Char (50) 50 bytes
emailAddress 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 muestra contiene cinco millones de filas y no está indexada. Ahora se analizará el rendimiento de varias consultas. Estos son una consulta mediante la identificación y uno (un campo clave ordenados) utilizando el primerNombre (sin ordenar un campo que no son clave).

Ejemplo 1 - campos ordenados vs 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 los bfr = (B/R) = 1024/204 = 5registros por bloque de disco. El número total de bloques necesarios para mantener la mesa es N = (r/bfr) = 5000000/5 = 1,000,000bloques.

Una búsqueda lineal en el campo de identificación requeriría un promedio de N/2 = 500,000accesos de bloque para encontrar un valor, dado que el campo de identificación es un campo clave. Pero como el campo de identificación también está ordenado, se puede realizar una búsqueda binaria que requiere un promedio de log2 1000000 = 19.93 = 20accesos de bloque. Al instante podemos ver que esto es 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, por lo que la tabla requerirá buscar hasta el final los N = 1,000,000accesos de un bloque exacto . Es esta situación 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 pensar que será más pequeño que el registro de campo múltiple al que apunta. Por lo tanto, el índice en sí mismo requiere menos bloques de disco que la tabla original, lo que, por lo tanto, requiere menos accesos de bloque para iterar. El esquema para un índice en el campo firstName se describe a continuación;

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

Nota : Los punteros en MySQL tienen una longitud de 2, 3, 4 o 5 bytes, dependiendo del 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 R = 54bytes de índice y utilizando los B = 1,024bytes de tamaño de bloque predeterminado . El factor de bloqueo del índice serían los 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 con el campo firstName 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 de bloque. Para encontrar la dirección del registro real, que requiere un acceso de bloque adicional para leer, llevando el total para 19 + 1 = 20bloquear los accesos, muy lejos de los 1,000,000 de accesos de bloque requeridos para encontrar una coincidencia de FirstName 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 adicionales 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 que los campos de indexación utilizados solo para la salida sean 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 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 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 "Full Table Scan" en el mundo de la base 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 de coincidencia, puede saltar eficientemente 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, por lo que totalmente 1010 páginas.

Por lo tanto, el índice es una sección separada que almacena los valores de la columna indexada + puntero a la fila indexada en un orden ordenado para búsquedas eficientes.

Las cosas son simples en las escuelas, ¿no es así? :PAGS

La primera vez que leí esto fue muy útil para mí. Gracias.

Desde entonces, obtuve algunas ideas sobre la desventaja de crear índices: si escribe en una tabla ( UPDATEo INSERT) con un índice, en realidad tiene dos operaciones de escritura en el sistema de archivos. Uno para los datos de la tabla y otro para los datos del índice (y el recurso de los mismos (y, si están agrupados, el recurso de los datos de la tabla)). Si la tabla y el índice se encuentran en el mismo disco duro, esto cuesta más tiempo. Por lo tanto, una tabla sin índice (un montón) permitiría operaciones de escritura más rápidas. (si tuviera dos índices, terminaría con tres operaciones de escritura, etc.)

Sin embargo, la definición de dos ubicaciones diferentes en dos discos duros diferentes para datos de índice y datos de tabla puede disminuir / eliminar el problema de un mayor costo de tiempo. Esto requiere la definición de grupos de archivos adicionales con los archivos correspondientes en los discos duros deseados y la definición de la ubicación de la tabla / índice según se desee.

Otro problema con los índices es su fragmentación en el tiempo a medida que se insertan los datos. REORGANIZEayuda, debes escribir rutinas para hacerlo.

En ciertos escenarios, un montón es más útil que una tabla con índices,

por ejemplo: - Si tiene muchas escrituras rivales pero solo una lectura nocturna fuera del horario comercial para informar.

Además, una diferenciación entre índices agrupados y no agrupados es bastante importante.

Me ayudó: - ¿Qué significan realmente el índice agrupado y no agrupado?

Un índice es solo una estructura de datos que acelera la búsqueda de una columna específica en una base de datos. Esta estructura suele ser un b-tree o una tabla hash, pero puede ser cualquier otra estructura lógica.

Ahora, supongamos que queremos ejecutar una consulta para encontrar todos los detalles de cualquier empleado que se llame 'Abc'.

SELECT * FROM Employee 
WHERE Employee_Name = 'Abc'

¿Qué pasaría sin un índice?

El software de base de datos literalmente tendría que mirar cada una de las filas de la tabla Empleado para ver si Employee_Name para esa fila es 'Abc'. Y, dado que queremos cada fila con el nombre 'Abc' dentro, no podemos dejar de buscar una vez que encontramos solo una fila con el nombre 'Abc', porque podría haber otras filas con el nombre Abc . Por lo tanto, cada fila hasta la última fila debe buscarse, lo que significa que la base de datos tendrá que examinar miles de filas en este escenario para encontrar las filas con el nombre 'Abc'. Esto es lo que se llama una exploración de tabla completa

Cómo un índice de base de datos puede ayudar al rendimiento

El objetivo principal de tener un índice es acelerar las consultas de búsqueda esencialmente reduciendo el número de registros / filas en una tabla que deben examinarse. Un índice es una estructura de datos (más comúnmente un árbol B) que almacena los valores para una columna específica en una tabla.

¿Cómo funciona el índice B-trees?

La razón por la que los árboles B son la estructura de datos más popular para los índices se debe al hecho de que son eficientes en el tiempo, ya que las búsquedas, eliminaciones e inserciones se pueden realizar en tiempo logarítmico. Y, otra razón principal por la que los árboles B se usan más comúnmente es porque los datos que se almacenan dentro del árbol B se pueden ordenar. El RDBMS generalmente determina qué estructura de datos se usa realmente para un índice. Pero, en algunos escenarios con ciertos RDBMS, puede especificar qué estructura de datos desea que use su base de datos cuando cree el índice.

¿Cómo funciona un índice de tabla hash?

La razón por la que se usan los índices hash es porque las tablas hash son extremadamente eficientes cuando se trata de buscar valores. Por lo tanto, las consultas que comparan la igualdad con una cadena pueden recuperar valores muy rápidamente si usan un índice hash.

Por ejemplo, la consulta que discutimos anteriormente podría beneficiarse de un índice hash creado en la columna Employee_Name. La forma en que funcionaría un índice hash es que el valor de la columna será la clave en la tabla hash y el valor real asignado a esa clave solo sería un puntero a los datos de fila en la tabla. Dado que una tabla hash es básicamente una matriz asociativa, una entrada típica se vería algo así como "Abc => 0x28939", donde 0x28939 es una referencia a la fila de la tabla donde Abc se almacena en la memoria. Buscar un valor como "Abc" en un índice de tabla hash y recuperar una referencia a la fila en la memoria es obviamente mucho más rápido que escanear la tabla para encontrar todas las filas con un valor de "Abc" en la columna Employee_Name.

Las desventajas de un índice hash

Las tablas hash no son estructuras de datos ordenadas, y hay muchos tipos de consultas con las que los índices hash ni siquiera pueden ayudar. Por ejemplo, suponga que desea conocer a todos los empleados que tienen menos de 40 años. ¿Cómo podrías hacer eso con un índice de tabla hash? Bueno, no es posible porque una tabla hash solo es buena para buscar pares de valores clave, lo que significa consultas que verifican la igualdad

¿Qué hay exactamente dentro de un índice de base de datos? Entonces, ahora sabe que se crea un índice de base de datos en una columna de una tabla y que el índice almacena los valores en esa columna específica. Pero, es importante comprender que un índice de base de datos no almacena los valores en las otras columnas de la misma tabla. Por ejemplo, si creamos un índice en la columna Employee_Name, esto significa que los valores de la columna Employee_Age y Employee_Address tampoco se almacenan en el índice. Si simplemente almacenamos todas las otras columnas en el índice, sería como crear otra copia de la tabla completa, lo que ocuparía demasiado espacio y sería muy ineficiente.

¿Cómo sabe una base de datos cuándo usar un índice? Cuando se ejecuta una consulta como "SELECT * FROM Employee WHERE Employee_Name = 'Abc'", la base de datos verificará si hay un índice en las columnas que se consultan. Suponiendo que la columna Employee_Name tiene un índice creado, la base de datos tendrá que decidir si realmente tiene sentido usar el índice para encontrar los valores que se están buscando, porque hay algunos escenarios en los que es menos eficiente usar el índice de la base de datos. , y más eficiente solo para escanear toda la tabla.

¿Cuál es el costo de tener un índice de base de datos?

Ocupa espacio, y cuanto mayor sea su tabla, mayor será su índice. Otro golpe de rendimiento con los índices es el hecho de que cada vez que agregue, elimine o actualice filas en la tabla correspondiente, se deberán realizar las mismas operaciones en su índice. Recuerde que un índice debe contener los mismos datos hasta el minuto que lo que esté en las columnas de la tabla que cubre el índice.

Como regla general, un índice solo debe crearse en una tabla si los datos de la columna indexada se consultarán con frecuencia.

Ver también

1. ¿Qué columnas generalmente hacen buenos índices?
2. ¿Cómo funcionan los índices de bases de datos?

Descripción simple!

El índice no es más que una estructura de datos que almacena los valores para una columna específica en una tabla. Se crea un índice en una columna de una tabla.

Ejemplo: tenemos una tabla de base de datos llamada Usercon tres columnas - Name, Agey Address. Suponga que la Usertabla tiene miles de filas.

Ahora, supongamos que queremos ejecutar una consulta para encontrar todos los detalles de cualquier usuario que se llame 'John'. Si ejecutamos la siguiente consulta:

SELECT * FROM User 
WHERE Name = 'John'

El software de la base de datos literalmente tendría que mirar cada fila de la Usertabla para ver si el Namede esa fila es 'John'. Esto tomará un largo tiempo.

Aquí es donde indexnos ayuda: el índice se utiliza para acelerar las consultas de búsqueda al reducir esencialmente el número de registros / filas en una tabla que debe examinarse .

Cómo crear un índice:

CREATE INDEX name_index
ON User (Name)

Una indexconsta de valores de columna (por ejemplo, John) de una tabla , y esos valores se almacenan en una estructura de datos .

Entonces, la base de datos usará el índice para encontrar empleados llamados John porque el índice probablemente se ordenará alfabéticamente por el nombre de los usuarios. Y, como está ordenado, significa que buscar un nombre es mucho más rápido porque todos los nombres que comienzan con una "J" estarán uno al lado del otro en el índice.

Solo una sugerencia rápida. Como la indexación le cuesta espacio adicional de escritura y almacenamiento, por lo que si su aplicación requiere más operaciones de inserción / actualización, es posible que desee usar tablas sin índices, pero si requiere más operaciones de recuperación de datos, debe ir a indexado mesa.

Solo piense en el índice de base de datos como índice de un libro.

Si tiene un libro sobre perros y desea encontrar información sobre, digamos, pastores alemanes, por supuesto, puede hojear todas las páginas del libro y encontrar lo que está buscando, pero esto, por supuesto, lleva mucho tiempo y no muy rapido.

Otra opción es que, simplemente puede ir a la sección Índice del libro y luego encontrar lo que está buscando utilizando el Nombre de la entidad que está buscando (en este caso, Pastores Alemanes) y también mirando el número de página para Encuentra rápidamente lo que estás buscando.

En la base de datos, el número de página se conoce como un puntero que dirige la base de datos a la dirección en el disco donde se encuentra la entidad. Usando la misma analogía del Pastor Alemán, podríamos tener algo como esto ("Pastor Alemán", 0x77129) donde 0x77129está la dirección en el disco donde se almacenan los datos de la fila del Pastor Alemán.

En resumen, un índice es una estructura de datos que almacena los valores de una columna específica en una tabla para acelerar la búsqueda de consultas.