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 y espacio de almacenamiento adicionales para mantener la estructura de datos del índice. Los índices se utilizan para localizar datos rápidamente sin tener que buscar en cada fila de una tabla de base de datos cada vez que se accede a dicha tabla. Los índices se pueden crear utilizando una o más columnas de una tabla de base de datos , lo que proporciona la base para búsquedas aleatorias rápidas y un acceso eficiente a 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 desde la cual se copió, para permitir recuperar la fila completa de manera eficiente. Algunas bases de datos amplían el poder de la indexación al permitir a los desarrolladores crear índices sobre valores de columnas 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 índice parcial , 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.
La mayoría del software de bases 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 ineficiente para bases de datos grandes.
Supongamos 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 según la prueba. Si solo hay un elemento coincidente, esto puede detenerse cuando encuentre ese elemento, pero si hay varias coincidencias, debe probarlo 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 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 búsqueda, el tamaño del índice y el rendimiento de 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)).
Los índices se utilizan para controlar las restricciones de la base de datos , como ÚNICA, EXCLUSIÓN, CLAVE PRIMARIA y CLAVE EXTRANJERA . Un índice puede declararse 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 CLAVE PRIMARIA, 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 referenciados como los referenciados en una restricción FOREIGN KEY estén indexados, mejorando así el rendimiento de las 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 sea válido 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 en la tabla intervalos de tiempo superpuestos ni objetos geométricos que se intersequen. Se requiere un índice que admita una búsqueda rápida de registros que satisfagan el predicado para controlar dicha restricción. [1]
Los datos están presentes en orden arbitrario, pero el orden lógico lo especifica el índice. Las filas de datos pueden estar distribuidas 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, 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,
Puede haber más de un índice no agrupado en una tabla de base de datos.
La agrupación altera el bloque de datos en un orden distinto para que coincida con el índice, lo que da como resultado que los datos de las filas se almacenen en orden. Por lo tanto, sólo se puede crear un índice agrupado en una tabla de base de datos determinada. Los índices agrupados pueden aumentar considerablemente la velocidad general de recuperación, pero generalmente solo cuando se accede a los datos secuencialmente en el mismo orden o en orden inverso al índice agrupado, o cuando se selecciona una variedad de elementos.
Dado que los registros físicos están en este orden de clasificación en el disco, el siguiente elemento de fila en la secuencia está inmediatamente antes o después del último, por lo que se requieren menos lecturas de bloques de datos. Por lo tanto, la característica principal de un índice agrupado es 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 y de índice en archivos separados, otras colocan dos bloques de datos completamente diferentes dentro de los mismos archivos físicos.
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 grupo 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 localizarlos. [2] 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 está definido por el valor de la clave del clúster.
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 una mayor.
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. Habrí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 comprueba la coincidencia con first_name. Por lo tanto, para mejorar el rendimiento, es necesario asegurarse de que el índice se cree en el orden de las columnas de búsqueda.
Los índices son útiles para muchas aplicaciones, pero tienen algunas limitaciones. Considere la siguiente declaración SQL : . Para procesar esta declaración sin un índice, el software de la base de datos debe mirar la columna apellido en cada fila de la tabla (esto se conoce como escaneo completo de la tabla ). Con un índice, la base de datos simplemente sigue la estructura de datos del índice (normalmente un árbol B ) hasta que se encuentra la entrada de Smith; esto es mucho menos costoso desde el punto de vista computacional que un escaneo completo de la tabla.SELECT first_name FROM people WHERE last_name = 'Smith';
Considere esta declaración SQL: . Esta consulta producirí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_correo electrónico ha sido indexada, la base de datos debe realizar un escaneo 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 principio 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 es sargable ). Este problema se puede resolver agregando otro índice creado y una consulta SQL como esta: . Esto coloca el comodín en la parte más derecha de la consulta (ahoraSELECT email_address FROM customers WHERE email_address LIKE '%@wikipedia.org';reverse(email_address)SELECT email_address FROM customers WHERE reverse(email_address) LIKE reverse('%@wikipedia.org');gro.aidepikiw@%), que el índice en reverso (dirección_correo electrónico) puede satisfacer.
Cuando se utilizan caracteres comodín en ambos lados de la palabra de búsqueda como %wikipedia.org% , no se utiliza el índice disponible en este campo. Más bien sólo se realiza una búsqueda secuencial, lo que lleva tiempo.
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 un pequeño número 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 suele contener 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 comúnmente utilizados.
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 en 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. [3]
Un índice disperso en las bases de datos es un archivo con pares de claves y punteros para cada bloque del 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 en cada bloque.
Un índice de clave inversa invierte el valor de la clave antes de ingresarlo en el índice. Por ejemplo, el valor 24538 pasa a ser 83542 en el índice. Invertir el valor clave es particularmente útil para indexar datos como números de secuencia, donde los nuevos valores clave aumentan monótonamente.
Un índice invertido asigna una palabra de contenido al documento que la contiene, permitiendo así búsquedas de texto completo.
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.
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 un campo clave o en un campo de 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.
Un índice hash en una base de datos es el índice más utilizado en la gestión de datos. Se crea en una columna que contiene valores únicos, como una clave principal o una dirección de correo electrónico.
Otro tipo de índice utilizado en los sistemas de bases de datos es el hash lineal .
Los índices se pueden implementar utilizando una variedad de estructuras de datos. Los índices populares incluyen árboles equilibrados , árboles B+ y hashes . [4]
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. [5] Cada relación puede tener un único índice agrupado y muchos índices no agrupados. [6]
Por lo general, varias transacciones y procesos acceden a un índice simultáneamente y, por lo tanto, necesita control de simultaneidad . 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 obtener una ganancia sustancial de rendimiento.
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 sólo se utiliza para localizar registros de datos en la tabla y no para devolver datos.
Un índice de cobertura es un caso especial en el que el índice mismo contiene los campos de datos requeridos y puede responder a los datos requeridos.
Considere la siguiente tabla (otros campos omitidos):
Para encontrar el nombre para el ID 13, es útil un índice en (ID), pero aún así se debe leer el registro 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 que SE UNEN/acceden a través de varias tablas pueden considerar cubrir índices en más de una de estas tablas. [7]
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 del índice, algunos sistemas permiten incluir campos no 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.
Esto se puede hacer en SQL con . [8] [9]CREATE INDEX my_index ON my_table (id) INCLUDE (name);
Ningún estándar define cómo crear índices, porque el Estándar ISO SQL no cubre 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 tablas o grupos de archivos). Todos los proveedores de RDBMS ofrecen una sintaxis con algunas opciones específicas que dependen de las capacidades de su software.CREATE INDEX
{{cite book}}: |work=ignorado ( ayuda )