Pregunta ¿Cómo funciona la indexación de bases de datos?


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

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


1873
2017-08-04 10:07


origen


Respuestas:


¿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 manera que las listas vinculadas; ambos contienen una sección para datos, un puntero a la ubicación del próximo nodo (o bloque), y ambos no necesitan almacenarse contiguamente.

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 es un campo que no es clave (es decir, no contiene entradas únicas), se debe buscar todo el espacio de tablas en N bloquear accesos.

Mientras que con un campo ordenado, se puede usar una búsqueda binaria, que tiene log2 N bloquear accesos. Además, dado que los datos se ordenan dado un campo no 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 en el rendimiento es sustancial.

¿Qué es la indexación?

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

La desventaja de indexar 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, perfilemos 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: char se usó 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. El rendimiento de varias consultas ahora será analizado. Estas son una consulta que usa el carné de identidad (un campo clave ordenado) y uno que usa el nombre de pila (un campo no clasificado sin clave).

Ejemplo 1 - ordenados vs campos sin clasificar

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

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

Ahora el nombre de pila el campo no está ordenado ni es un campo clave, por lo que una búsqueda binaria es imposible, y los valores no son únicos, por lo que la tabla requerirá buscar hasta el final para obtener una 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 razonable pensar que será más pequeño que el registro de campo múltiple al que apunta. Por lo tanto, el índice en sí requiere menos bloques de disco que la tabla original, por lo que requiere menos accesos de bloque para iterar. El esquema para un índice en el nombre de pila el campo se describe a continuación;

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

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. La cantidad total de bloques necesarios para mantener el índice es N = (r/bfr) = 5000000/18 = 277,778 bloques.

Ahora una búsqueda usando el nombre de pila 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 bloquear los accesos, muy lejos de los 1,000,000 de bloques de acceso requeridos para encontrar un nombre de pila coincide en la tabla no indexada.

¿Cuándo debería usarse?

Dado que crear un índice requiere espacio de disco adicional (277,778 bloques adicionales del ejemplo anterior, un ~ 28% de aumento), 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 para indexar

Dado que los índices solo se utilizan 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 un desperdicio de espacio en disco y tiempo de procesamiento al realizar una operación de inserción o eliminación, y así 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 un tipo lineal, y el optimizador de consultas evitará usar el índice si la cardinalidad es menor al 30% del número de registro, lo que hace que el índice sea una pérdida de espacio.


2848
2017-08-04 10:41



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 (UPDATE o INSERT) con un índice, 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 a él (y, si está agrupado, el recurso a los datos de la tabla)). Si la tabla y el índice están ubicados 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, y así sucesivamente)

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

Otro problema con los índices es su fragmentación en el tiempo a medida que se insertan los datos. REORGANIZE ayuda, debe escribir rutinas para que se haga.

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é significa realmente el índice agrupado y no agrupado?


175
2018-04-30 14:31



Un índice es solo una estructura de datos que hace que la búsqueda sea más rápida para 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.

Para más información, recomiendo: ¿Cómo funcionan los índices de base de datos? Y, ¿cómo ayudan los índices?


130
2018-02-20 14:40



Ahora, digamos que queremos ejecutar una consulta para encontrar todos los detalles de los empleados que se llaman 'Abc'?

SELECT * FROM Employee 
WHERE Employee_Name = 'Abc'

¿Qué pasaría sin un índice?

El software de base de datos tendría que ver literalmente cada fila de la tabla Employee para ver si Employee_Name para esa fila es 'Abc'. Y, como queremos que cada fila con el nombre 'Abc' dentro, no podemos dejar de buscar una vez que encontramos una sola fila con el nombre 'Abc', porque podría haber otras filas con el nombre A B C. 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 escaneo de tabla completo

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

El objetivo de tener un índice es acelerar las consultas de búsqueda reduciendo esencialmente el número de registros / filas en una tabla que debe 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 cual B-trees es la estructura de datos más popular para los índices se debe a 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 importante por la cual los árboles B- se usan más comúnmente es porque los datos que se almacenan dentro del árbol B se pueden clasificar. 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 crea el índice.

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

La razón por la que se utilizan los índices hash es porque las tablas hash son extremadamente eficientes cuando se trata solo de buscar valores. Por lo tanto, las consultas que se comparan por igualdad con una cadena pueden recuperar valores muy rápido 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 de hash es que el valor de la columna será la clave en la tabla de hash y el valor real asignado a esa clave solo será un puntero a los datos de la fila en la tabla. Como una tabla hash es básicamente una matriz asociativa, una entrada típica se vería como "Abc => 0x28939", donde 0x28939 es una referencia a la fila de la tabla donde se almacena Abc 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, supongamos que desea conocer a todos los empleados que tienen menos de 40 años. ¿Cómo podrías hacer eso con un índice de tablas hash? Bueno, no es posible porque una tabla hash solo sirve 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 en una tabla, y que el índice almacena los valores en esa columna específica. Sin embargo, 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 solo 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 la (s) columna (s) que se está (n) consultando. Suponiendo que la columna Employee_Name tiene un índice creado en ella, la base de datos tendrá que decidir si realmente tiene sentido usar el índice para encontrar los valores que se buscan, porque hay algunos escenarios en los que en realidad 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 más grande sea su mesa, 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, las mismas operaciones tendrán que realizarse en su índice. Recuerde que un índice debe contener los mismos datos de última hora que cualquier columna de la tabla que cubra el índice.

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

Ver también

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

93
2017-08-13 18:36



Ejemplo clásico "Índice en libros"

Considere un "Libro" de 1000 páginas, dividido por 100 secciones, cada sección con X páginas.

Simple, ¿eh?

Ahora, sin una página de índice, para encontrar una sección particular que comienza con la letra "S", no tiene otra opción que escanear todo el libro. es decir: 1000 páginas

Pero con una página de índice al comienzo, estás allí. Y más, para leer cualquier sección en particular que importe, 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 la sección omitiendo otras secciones.

Pero luego, además de 1000 páginas, necesitará otras ~ 10 páginas para mostrar la página de índice, por lo que tendrá 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 efectivas.

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


82
2018-04-23 14:43



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 Usuario con tres columnas: Nombre, Edad y Dirección. Supongamos que la tabla de usuario tiene miles de filas.

Ahora, digamos que queremos ejecutar una consulta para encontrar todos los detalles de los usuarios que se llaman 'John'. Si ejecutamos la siguiente consulta.

SELECT * FROM User 
WHERE Name = 'John'

El software de la base de datos tendría que ver literalmente cada fila en la tabla de Usuario para ver si el Nombre de esa fila es 'John'. Esto llevará un largo tiempo.
Aquí es donde el índice nos ayuda "el índice se usa 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)

Un índice consta de valores de columna (por ejemplo, John) de una tabla, y esos valores se almacenan en una estructura de datos.
Así que ahora la base de datos usará el índice para encontrar empleados llamados John porque el índice presumiblemente estará ordenado 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.


46
2017-08-02 01:30



Solo una sugerencia rápida. Como la indexación le cuesta escrituras adicionales y espacio de almacenamiento, entonces si su aplicación requiere más operaciones de inserción / actualización, puede usar tablas sin índices, pero si requiere más operaciones de recuperación de datos, debe ir por indexado mesa.


21
2018-01-14 06:44



Solo piense en el índice de la base de datos como índice de un libro.  Si tiene un libro sobre perros y quiere encontrar una información sobre, por ejemplo, German Shepherds, podría hojear todas las páginas del libro y encontrar lo que está buscando, pero esto, por supuesto, consume mucho tiempo y no es muy rápido. Otra opción es que, simplemente, vaya a la sección de índice del libro y luego encuentre lo que está buscando utilizando el nombre de la entidad que está buscando (en este caso, los pastores alemanes) y también mirando el número de página a encuentre rápidamente lo que está 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 de Pastor Alemán, podríamos tener algo como esto ("Pastor Alemán", 0x77129) donde 0x77129 es la dirección en el disco donde se almacenan los datos de fila para 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.


16
2017-12-21 17:16