Índice de la base de datos

La mayoría del software de bases de datos incluye tecnología de indexación que permite búsquedas en 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 y que se debe recuperar uno de ellos en función del valor de uno de sus campos. Una implementación sencilla recupera y examina cada elemento según la prueba. Si solo hay un elemento coincidente, el proceso se detiene al encontrarlo; pero si hay varios, debe probarlos todos. Esto significa que el número de operaciones, en 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, suele ser deseable mejorar el rendimiento.

Un índice es cualquier estructura de datos que mejora el rendimiento de las búsquedas. Existen diversas estructuras de datos utilizadas para este fin. El diseño implica complejas compensaciones en cuanto al rendimiento de las búsquedas, el tamaño del índice y el rendimiento de su actualización. Muchos diseños de índices presentan un rendimiento de búsqueda logarítmico ( O (log(N))) y, en algunas aplicaciones, es posible alcanzar un rendimiento plano ( O (1)).

Los índices se utilizan para controlar las restricciones de la base de datos , como UNIQUE, EXCLUSION, PRIMARY KEY y FOREIGN KEY . Un índice puede declararse como UNIQUE, lo que crea una restricción implícita en la tabla subyacente. Los sistemas de bases de datos suelen crear implícitamente un índice en un conjunto de columnas declaradas como PRIMARY KEY, y algunos pueden utilizar un índice ya existente para controlar esta restricción. Muchos sistemas de bases de datos requieren que tanto las columnas que hacen referencia como las que son referenciadas en una restricción FOREIGN KEY estén indexadas, lo que mejora 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 predicado determinado no se cumpla para ningún otro registro. Esto se puede usar para implementar una restricción UNIQUE (con predicado de igualdad) o restricciones más complejas, como garantizar que no se almacenen en la tabla rangos de tiempo superpuestos ni objetos geométricos que se intersequen. Se requiere un índice que permita una búsqueda rápida de los registros que satisfacen el predicado para controlar dicha restricción. ^{[ 2 ]}

Los datos se presentan en un 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 ordenadas, y el nivel hoja del índice contiene el puntero al registro (página y número de fila en la página de datos en motores organizados por página; desplazamiento de fila en motores organizados por archivo).

En un índice no agrupado,

• El orden físico de las filas no coincide con el orden del índice.
• Las columnas indexadas suelen ser columnas que no son clave primaria y que se utilizan en las cláusulas JOIN, WHERE y ORDER BY.

Una tabla de base de datos puede tener más de un índice no agrupado.

La agrupación modifica el bloque de datos para que coincida con el índice, lo que permite almacenar los datos de las filas en orden. Por lo tanto, solo se puede crear un índice agrupado en una tabla de base de datos. Los índices agrupados pueden aumentar considerablemente la velocidad de recuperación, pero generalmente solo cuando se accede a los datos de forma secuencial, en el mismo orden o en orden inverso al del índice agrupado, o cuando se selecciona un rango de elementos.

Dado que los registros físicos se encuentran ordenados de esta manera en el disco, la siguiente fila de la secuencia se ubica inmediatamente antes o después de la última, lo que reduce la cantidad de lecturas de bloques de datos. Por lo tanto, la característica principal de un índice agrupado es la ordenación de las filas de datos físicas según los bloques de índice que las referencian. Algunas bases de datos separan los bloques de datos y de índice en archivos distintos, mientras que otras colocan dos bloques de datos completamente diferentes dentro del mismo archivo o archivos físicos.

Cuando se combinan varias bases de datos y varias tablas, se denomina clúster (que 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 de datos cercanos. Esto puede mejorar las combinaciones de estas tablas en la clave de clúster, ya que los registros coincidentes se almacenan juntos y se requiere menos E/S para localizarlos. ^{[ 3 ]} La configuración del clúster define la disposición de los datos en las tablas que forman parte del clúster. Un clúster puede estar indexado mediante un índice B-tree o una tabla hash . El bloque de datos donde se almacena el registro de la tabla se define mediante el valor de la clave de clúster.

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 sobre 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 pocas veces. En cambio, 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 "sexo" en una base de datos de clientes suele contener como máximo tres valores distintos: masculino, femenino o desconocido (no registrado). Para este tipo de variables, el índice de mapa de bits puede ofrecer 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 específico a un registro en el archivo de datos ordenado. En índices agrupados con claves duplicadas, el índice denso apunta al primer registro con esa clave. ^{[ 4 ]}

En las bases de datos, un índice disperso es un archivo con pares de claves y punteros para cada bloque del archivo de datos. Cada clave de este archivo está asociada a un puntero específico que apunta al bloque correspondiente en el archivo de datos ordenado. En los índices agrupados con claves duplicadas, el índice disperso apunta a la clave de búsqueda más baja de cada bloque.

Un índice de clave inversa invierte el valor de la clave antes de insertarlo en el índice. Por ejemplo, el valor 24538 se convierte en 83542 en el índice. Invertir el valor de la clave es especialmente útil para indexar datos como números de secuencia, donde los nuevos valores de clave aumentan monótonamente.

Un índice invertido asocia una palabra clave con el documento que la contiene, lo que permite realizar búsquedas de texto completo.

El índice primario contiene los campos clave de la tabla y un puntero a los campos no clave. Este índice se crea automáticamente al crear la tabla en la base de datos.

Se utiliza para indexar campos que no son ni campos de ordenación ni campos clave (no hay garantía de que el archivo esté organizado por campos clave o clave primaria). Cada tupla del archivo de datos contiene una entrada de índice (índice denso) con el valor del atributo indexado y un puntero al bloque o registro.

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

Un índice suele ser accedido simultáneamente por varias transacciones y procesos, por lo que requiere control de concurrencia . Si bien, en principio, los índices pueden utilizar los métodos comunes de control de concurrencia de bases de datos, existen métodos especializados que se aplican junto con los comunes para lograr una mejora sustancial del rendimiento.