Índice de base de datos

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 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 que la fila completa se recupere 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 campo last_name en el índice. Otra opción que a veces se admite es el uso de índice parcial, donde las entradas del í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 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 según el 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)).

Vigilancia de las restricciones de la base de datos

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 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 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.

Arquitectura de índice y métodos de indexación

No agrupado

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,

• El orden físico de las filas no es el mismo que el orden índice.
• Las columnas indexadas son típicamente columnas clave no primarias utilizadas 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.

Agrupada

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 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 del í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.

Clúster

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. 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 de árbol B 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.

Orden de columnas

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 utilizan el índice.

En el ejemplo de la guía telefónica con un índice compuesto creado en las columnas (ciudad, apellido, nombre), si buscamos dando valores exactos para los tres campos, el tiempo de búsqueda es mínimo, pero Si proporcionamos los valores para city y first_name únicamente, la búsqueda utiliza solo el campo city 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.

Aplicaciones y limitaciones

Los índices son útiles para muchas aplicaciones, pero tienen algunas limitaciones. Considere la siguiente declaración SQL: SELECT nombre DESDE personas DÓNDE apellido = 'Smith';< /código>. 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.

Considere esta declaración SQL: SELECCIONAR dirección_correo electrónico DESDE clientes DÓNDE dirección_correo electrónico ME GUSTA '%@wikipedia.org' ;. Esta consulta arrojarí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 en reverse( email_address) y una consulta SQL como esta: SELECCIONAR dirección de correo electrónico DE clientes DÓNDE inversa(< span class="n">dirección_correo electrónico) ME GUSTA reverso(' %@wikipedia.org');. Esto coloca el comodín en la parte más derecha de la consulta (ahora gro.aidepikiw@%), que el índice en reverso (dirección_correo electrónico) puede satisfacer.

Cuando los caracteres comodín se utilizan en ambos lados de la palabra de búsqueda como %wikipedia.org, el índice disponible en este campo no se utiliza. Más bien sólo se realiza una búsqueda secuencial, que toma ${\displaystyle O(N)}$ tiempo.

Tipos de índices

Índice de mapas de bits

Un índice de bitmap es un tipo especial de indexación que almacena la mayor parte de sus datos como arrays de bits (bitmaps) y responde a la mayoría de las consultas realizando operaciones lógicas bitwise en estos bitmaps. Los índices más utilizados, como los árboles B+, son más eficientes si los valores que indexan no repiten ni repiten un pequeño número de veces. En cambio, el índice de bitmap está diseñado para casos en los que los valores de una variable se repiten muy frecuentemente. Por ejemplo, el campo sexual en una base de datos de clientes generalmente contiene en la mayoría de tres valores distintos: masculino, femenino o desconocido (no registrado). Para tales variables, el índice de mapas de bits puede tener una ventaja de rendimiento significativa sobre los árboles comúnmente utilizados.

Índice denso

Un índice denso en bases de datos es un archivo con pares de claves y punteros para cada registro en el 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.

Índice escaso

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.

Índice inverso

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.

Índice invertido

Un índice invertido asigna una palabra de contenido al documento que la contiene, permitiendo así búsquedas de texto completo.

Í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 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.

Índice hash

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.

Hashing lineal

Otro tipo de índice utilizado en los sistemas de bases de datos es el hash lineal.

Implementaciones de índice

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 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.

Í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 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 se omiten):

Para encontrar el nombre del 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.

Un índice de cobertura puede acelerar drásticamente la recuperación de datos, pero puede ser grande debido a las claves adicionales, que frenan la inserción y actualización de datos. Para reducir ese tamaño de índice, algunos sistemas permiten incluir campos no clave en el índice. Los campos no clave no son en sí mismos parte de la orden de índice, pero sólo se incluyen a nivel de hoja, permitiendo un índice de cobertura con menor tamaño de índice global.

Esto se puede hacer en SQL con CREAR ÍNDICE mi_índice ON mi_tabla (id) INCLUIR (nombre);.

Estandarización

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 un CREATE< /span> INDEX sintaxis con algunas opciones específicas que dependen de las capacidades de su software.