Índice de base de datos - Database index
Un índice de base de datos es una estructura de datos que mejora la velocidad de las operaciones de recuperación de datos en una tabla de base de datos a costa de escrituras adicionales y espacio de almacenamiento para mantener la estructura de datos del índice. Los índices se utilizan para ubicar datos rápidamente sin tener que buscar cada fila en una tabla de base de datos cada vez que se accede a una tabla de base de datos. Los índices se pueden crear utilizando una o más columnas de una tabla de base de datos , lo que proporciona la base tanto para búsquedas aleatorias rápidas como para un acceso eficiente a los registros ordenados.
Un índice es una copia de columnas de datos seleccionadas, de una tabla, que está diseñada para permitir una búsqueda muy eficiente. Un índice normalmente incluye una "clave" o enlace directo a la fila original de datos de la que se copió, para permitir que la fila completa se recupere de manera eficiente. Algunas bases de datos amplían el poder de la indexación al permitir que los desarrolladores creen índices en valores de columna que han sido transformados por funciones o expresiones . Por ejemplo, se podría crear un índice en upper(last_name), que solo almacenaría las versiones en mayúsculas del last_namecampo en el índice. Otra opción que a veces se admite es el uso de índices parciales , donde las entradas de índice se crean solo para aquellos registros que satisfacen alguna expresión condicional. Otro aspecto de la flexibilidad es permitir la indexación de funciones definidas por el usuario , así como expresiones formadas a partir de una variedad de funciones integradas.
Uso
Soporte para búsqueda rápida
La mayoría del software de base de datos incluye tecnología de indexación que permite la búsqueda de tiempo sublineal para mejorar el rendimiento, ya que la búsqueda lineal es ineficaz para bases de datos grandes.
Suponga que una base de datos contiene N elementos de datos y se debe recuperar uno en función del valor de uno de los campos. Una implementación simple recupera y examina cada elemento de acuerdo con la prueba. Si solo hay un elemento coincidente, esto puede detenerse cuando encuentra ese único elemento, pero si hay varias coincidencias, debe probar todo. Esto significa que el número de operaciones en el caso promedio es O (N) o tiempo lineal . Dado que las bases de datos pueden contener muchos objetos, y dado que la búsqueda es una operación común, a menudo es deseable mejorar el rendimiento.
Un índice es cualquier estructura de datos que mejora el rendimiento de la búsqueda. Hay muchas estructuras de datos diferentes que se utilizan para este propósito. Existen complejas compensaciones de diseño que involucran el rendimiento de la búsqueda, el tamaño del índice y el rendimiento de la actualización del índice. Muchos diseños de índices exhiben un rendimiento de búsqueda logarítmico ( O (log (N))) y en algunas aplicaciones es posible lograr un rendimiento plano ( O (1)).
Vigilancia de las limitaciones de la base de datos
Los índices se utilizan para controlar las restricciones de la base de datos , como ÚNICO, EXCLUSIÓN, CLAVE PRIMARIA y CLAVE EXTRANJERA . Un índice se puede declarar como ÚNICO, lo que crea una restricción implícita en la tabla subyacente. Los sistemas de bases de datos generalmente crean implícitamente un índice en un conjunto de columnas declaradas PRIMARY KEY, y algunos son capaces de usar un índice ya existente para controlar esta restricción. Muchos sistemas de bases de datos requieren que tanto los conjuntos de columnas de referencia como los referenciados en una restricción FOREIGN KEY estén indexados, mejorando así el rendimiento de inserciones, actualizaciones y eliminaciones en las tablas que participan en la restricción.
Algunos sistemas de bases de datos admiten una restricción de EXCLUSIÓN que garantiza que, para un registro recién insertado o actualizado, un determinado predicado no se mantenga para ningún otro registro. Esto se puede usar para implementar una restricción ÚNICA (con predicado de igualdad) o restricciones más complejas, como garantizar que no se almacenen rangos de tiempo superpuestos ni objetos geométricos que se crucen en la tabla. Se requiere un índice que admita la búsqueda rápida de registros que satisfagan el predicado para controlar tal restricción.
Arquitectura de índices y métodos de indexación
No agrupado
Los datos están presentes en un orden arbitrario, pero el orden lógico lo especifica el índice. Las filas de datos se pueden distribuir por toda la tabla independientemente del valor de la columna o expresión indexada. El árbol de índice no agrupado contiene las claves de índice en orden ordenado, con el nivel de hoja del índice que contiene el puntero al registro (página y el número de fila en la página de datos en motores organizados por páginas; desplazamiento de fila en motores organizados por archivos ).
En un índice no agrupado,
- El orden físico de las filas no es el mismo que el orden del índice.
- Las columnas indexadas suelen ser columnas de clave no principal que se utilizan en las cláusulas JOIN, WHERE y ORDER BY.
Puede haber más de un índice no agrupado en una tabla de base de datos.
Agrupado
La agrupación altera el bloque de datos en un cierto orden distinto para que coincida con el índice, lo que da como resultado que los datos de la fila se almacenen en orden. Por lo tanto, solo se puede crear un índice agrupado en una tabla de base de datos determinada. Los índices agrupados pueden aumentar en gran medida la velocidad general de recuperación, pero generalmente solo cuando se accede a los datos de forma secuencial en el mismo orden o en orden inverso al índice agrupado, o cuando se selecciona un rango de elementos.
Dado que los registros físicos están en este orden de clasificación en el disco, el siguiente elemento de la fila en la secuencia es inmediatamente antes o después del último, por lo que se requieren menos lecturas de bloques de datos. La característica principal de un índice agrupado es, por lo tanto, el orden de las filas de datos físicos de acuerdo con los bloques de índice que apuntan a ellas. Algunas bases de datos separan los bloques de datos e índices en archivos separados, otras colocan dos bloques de datos completamente diferentes dentro del mismo archivo físico.
Grupo
Cuando se unen varias bases de datos y varias tablas, se denomina clúster (no debe confundirse con el índice agrupado descrito anteriormente). Los registros de las tablas que comparten el valor de una clave de clúster se almacenarán juntos en el mismo bloque de datos o en bloques cercanos. Esto puede mejorar las uniones de estas tablas en la clave del clúster, ya que los registros coincidentes se almacenan juntos y se requiere menos E / S para ubicarlos. La configuración del clúster define el diseño de los datos en las tablas que forman parte del clúster. Un clúster se puede codificar con un índice B-Tree o una tabla hash . El bloque de datos donde se almacena el registro de la tabla se define por el valor de la clave del clúster.
Orden de columna
El orden en el que la definición del índice define las columnas es importante. Es posible recuperar un conjunto de identificadores de fila utilizando solo la primera columna indexada. Sin embargo, no es posible ni eficiente (en la mayoría de las bases de datos) recuperar el conjunto de identificadores de fila utilizando solo la segunda columna indexada o más.
Por ejemplo, en una guía telefónica organizada primero por ciudad, luego por apellido y luego por nombre, en una ciudad en particular, se puede extraer fácilmente la lista de todos los números de teléfono. Sin embargo, sería muy tedioso encontrar todos los números de teléfono de un apellido en particular. Uno tendría que buscar dentro de la sección de cada ciudad las entradas con ese apellido. Algunas bases de datos pueden hacer esto, otras simplemente no usan el índice.
En el ejemplo de la guía telefónica con un índice compuesto creado en las columnas ( city, last_name, first_name), si buscamos dando valores exactos para los tres campos, el tiempo de búsqueda es mínimo, pero si proporcionamos los valores para cityy first_namesolo, la búsqueda usa solo el citycampo para recuperar todos los registros coincidentes. Luego, una búsqueda secuencial verifica la coincidencia con first_name. Por lo tanto, para mejorar el rendimiento, uno debe asegurarse de que el índice se cree en el orden de las columnas de búsqueda.
Aplicaciones y limitaciones
Los índices son útiles para muchas aplicaciones, pero tienen algunas limitaciones. Considere el siguiente SQL declaración: SELECT first_name FROM people WHERE last_name = 'Smith';. Para procesar esta declaración sin un índice, el software de la base de datos debe mirar la columna last_name en cada fila de la tabla (esto se conoce como un escaneo completo de la tabla ). Con un índice, la base de datos simplemente sigue la estructura de datos del índice (típicamente un árbol B ) hasta que se encuentra la entrada de Smith; esto es mucho menos costoso computacionalmente que un escaneo de tabla completo.
Considere esta sentencia SQL: SELECT email_address FROM customers WHERE email_address LIKE '%@wikipedia.org';. Esta consulta generaría una dirección de correo electrónico para cada cliente cuya dirección de correo electrónico termine en "@ wikipedia.org", pero incluso si la columna dirección_de_correo electrónico se ha indexado, la base de datos debe realizar un análisis de índice completo. Esto se debe a que el índice se construye asumiendo que las palabras van de izquierda a derecha. Con un comodín al comienzo del término de búsqueda, el software de la base de datos no puede utilizar la estructura de datos del índice subyacente (en otras palabras, la cláusula WHERE no se puede comparar ). Este problema puede ser resuelto a través de la adición de otro índice creado en reverse(email_address)y una consulta SQL como esto: SELECT email_address FROM customers WHERE reverse(email_address) LIKE reverse('%@wikipedia.org');. Esto coloca el comodín en la parte más a la derecha de la consulta (ahora gro.aidepikiw@%), que el índice al revés (email_address) puede satisfacer.
Cuando los caracteres comodín se utilizan en ambos lados de la palabra de búsqueda como % wikipedia.org% , no se utiliza el índice disponible en este campo. Más bien, solo se realiza una búsqueda secuencial, lo que lleva O (N) tiempo.
Tipos de índices
Índice de mapa de bits
Un índice de mapa de bits es un tipo especial de indexación que almacena la mayor parte de sus datos como matrices de bits (mapas de bits) y responde a la mayoría de las consultas realizando operaciones lógicas bit a bit en estos mapas de bits. Los índices más utilizados, como los árboles B + , son más eficientes si los valores que indexan no se repiten o se repiten una pequeña cantidad de veces. Por el contrario, el índice de mapa de bits está diseñado para casos en los que los valores de una variable se repiten con mucha frecuencia. Por ejemplo, el campo de sexo en una base de datos de clientes generalmente contiene como máximo tres valores distintos: masculino, femenino o desconocido (no registrado). Para tales variables, el índice de mapa de bits puede tener una ventaja de rendimiento significativa sobre los árboles de uso común.
Índice denso
Un índice denso en bases de datos es un archivo con pares de claves y punteros para cada registro del archivo de datos. Cada clave de este archivo está asociada con un puntero particular a un registro en el archivo de datos ordenados. En índices agrupados con claves duplicadas, el índice denso apunta al primer registro con esa clave.
Índice escaso
Un índice disperso en bases de datos es un archivo con pares de claves y punteros para cada bloque en el archivo de datos. Cada clave en este archivo está asociada con un puntero particular al bloque en el archivo de datos ordenados. En índices agrupados con claves duplicadas, el índice disperso apunta a la clave de búsqueda más baja de cada bloque.
Índice inverso
Un índice de clave inversa invierte el valor de la clave antes de ingresarlo en el índice. Por ejemplo, el valor 24538 se convierte en 83542 en el índice. La inversión del valor de clave es particularmente útil para indexar datos como números de secuencia, donde los nuevos valores de clave aumentan monótonamente.
Índice primario
El índice principal contiene los campos clave de la tabla y un puntero a los campos no clave de la tabla. El índice principal se crea automáticamente cuando se crea la tabla en la base de datos.
Índice secundario
Se utiliza para indexar campos que no son campos de orden ni campos clave (no hay garantía de que el archivo esté organizado en el campo clave o en el campo clave principal). Una entrada de índice para cada tupla en el archivo de datos (índice denso) contiene el valor del atributo indexado y el puntero al bloque o registro.
Índice hash
Implementaciones de índices
Los índices se pueden implementar utilizando una variedad de estructuras de datos. Los índices populares incluyen árboles equilibrados , árboles B + y hashes .
En Microsoft SQL Server , el nodo hoja del índice agrupado corresponde a los datos reales, no simplemente un puntero a datos que residen en otro lugar, como es el caso de un índice no agrupado. Cada relación puede tener un único índice agrupado y muchos índices no agrupados.
Control de simultaneidad de índices
Por lo general, varias transacciones y procesos acceden simultáneamente a un índice y, por lo tanto, necesita control de concurrencia . Si bien, en principio, los índices pueden utilizar los métodos de control de concurrencia de bases de datos comunes, existen métodos de control de concurrencia especializados para índices, que se aplican junto con los métodos comunes para una mejora sustancial del rendimiento.
Índice de cobertura
En la mayoría de los casos, se utiliza un índice para localizar rápidamente los registros de datos de los que se leen los datos requeridos. En otras palabras, el índice solo se usa para ubicar registros de datos en la tabla y no para devolver datos.
Un índice de cobertura es un caso especial en el que el índice en sí contiene los campos de datos requeridos y puede responder a los datos requeridos.
Considere la siguiente tabla (otros campos omitidos):
| IDENTIFICACIÓN | Nombre | Otros campos |
|---|---|---|
| 12 | Enchufar | ... |
| 13 | Lámpara | ... |
| 14 | Fusible | ... |
Para encontrar el Nombre para el ID 13, es útil un índice en (ID), pero el registro aún debe leerse para obtener el Nombre. Sin embargo, un índice en (ID, Nombre) contiene el campo de datos requerido y elimina la necesidad de buscar el registro.
Los índices de cobertura son cada uno para una tabla específica. Las consultas a las que JOIN / acceden a través de múltiples tablas, pueden potencialmente considerar cubrir índices en más de una de estas tablas.
Un índice de cobertura puede acelerar drásticamente la recuperación de datos, pero en sí mismo puede ser grande debido a las claves adicionales, que ralentizan la inserción y actualización de datos. Para reducir dicho tamaño de índice, algunos sistemas permiten incluir campos que no son clave en el índice. Los campos que no son clave no son en sí mismos parte del orden del índice, sino que solo se incluyen a nivel de hoja, lo que permite un índice de cobertura con un tamaño de índice general menor.
Estandarización
Ningún estándar define cómo crear índices, porque el estándar ISO SQL no cubre los aspectos físicos. Los índices son una de las partes físicas de la concepción de una base de datos, entre otras, como el almacenamiento (espacio de tabla o grupos de archivos). Todos los proveedores de RDBMS ofrecen una sintaxis CREATE INDEX con algunas opciones específicas que dependen de las capacidades de su software.