Índice de base de datos

Este artículo necesita citas adicionales para su verificación . Por favor, ayude a mejorar este artículo añadiendo citas de fuentes fiables . El material sin fuentes puede ser cuestionado y eliminado. Buscar fuentes:  «Índice de base de datos» – noticias  · periódicos  · libros  · académico  · JSTOR ( mayo de 2024 ) ( Aprenda cómo y cuándo eliminar este mensaje )

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 tanto para búsquedas aleatorias rápidas como para 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 un enlace directo a la fila original de datos de la que se copió, para permitir que se recupere la fila completa de manera eficiente. Algunas bases de datos extienden el poder de la indexación al permitir que los desarrolladores creen índices en valores de columna que se han transformado mediante 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 un índice parcial , donde las entradas de índice se crean solo para aquellos registros que satisfacen alguna expresión condicional. Un aspecto adicional de la flexibilidad es permitir la indexación en 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 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 de datos y se debe recuperar uno en función del valor de uno de los campos. Una implementación sencilla recupera y examina cada elemento según la prueba. Si solo hay un elemento coincidente, esto puede detenerse cuando encuentra ese único elemento, pero si hay múltiples 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 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. Existen 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 presentan 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 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 PRIMARY KEY, y algunos son capaces de utilizar 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 de las tablas que participan en la restricción.

Algunos sistemas de bases de datos admiten una restricción EXCLUSION que garantiza que, para un registro recién insertado o actualizado, un predicado determinado no se cumple para ningún otro registro. Esto se puede utilizar para implementar una restricción UNIQUE (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. Para controlar dicha restricción se requiere un índice que admita la búsqueda rápida de registros que satisfagan el predicado. ^[1]

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 en orden ordenado, y el nivel de 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á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 normalmente son 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.

La agrupación en clústeres altera el bloque de datos en un orden determinado para que coincida con el índice, lo que hace que los datos de las filas 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 considerablemente la velocidad general de recuperación, pero normalmente 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 en este orden de clasificación en el disco, el siguiente elemento de la fila en la secuencia se encuentra 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 ordenamiento de las filas de datos físicos de acuerdo con los bloques de índice que las apuntan. Algunas bases de datos separan los bloques de datos e índice en archivos separados, mientras que 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 ( 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 los mismos bloques de datos o en bloques cercanos. Esto puede mejorar las uniones 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. ^[2] La configuración del clúster define el diseño de datos en las tablas que forman parte del clúster. Un clúster puede tener una clave con un índice de árbol B 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.

El orden en 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 superior.

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 para 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 ( city, last_name, first_name), si buscamos proporcionando valores exactos para los tres campos, el tiempo de búsqueda es mínimo, pero si proporcionamos los valores para cityy first_namesolamente, la búsqueda utiliza solamente 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.

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 base de datos debe observar 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 (normalmente un árbol B ) hasta que se encuentra la entrada Smith; esto es mucho menos costoso computacionalmente que un escaneo completo de la tabla.SELECT first_name FROM people WHERE last_name = 'Smith';

Considere esta declaración SQL: . Esta consulta generaría una dirección de correo electrónico para cada cliente cuya dirección de correo electrónico termine con "@wikipedia.org", pero incluso si la columna email_address ha sido indexada, la base de datos debe realizar un escaneo completo del índice. Esto se debe a que el índice se construye con el supuesto de 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 usar la estructura de datos del índice subyacente (en otras palabras, la cláusula WHERE no se puede buscar en la base de datos ). Este problema se puede resolver mediante la adición de otro índice creado en y una consulta SQL como esta: . Esto coloca el comodín en la parte más a la 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 reverse(email_address) 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. En su lugar, solo se realiza una búsqueda secuencial, que lleva tiempo${\displaystyle O(N)}$ .

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.

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 a un puntero particular a un registro del archivo de datos ordenado. En índices agrupados con claves duplicadas, el índice denso apunta al primer registro con esa clave. ^[3]

Un índice disperso en bases de datos 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 particular al bloque del archivo de datos ordenado. En í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 introducirlo en el índice. Por ejemplo, el valor 24538 se convierte en 83542 en el índice. Invertir el valor de la clave es particularmente útil para indexar datos como números de secuencia, donde los nuevos valores de clave aumentan de forma monótona.

Un índice invertido asigna una palabra de contenido al documento que la contiene, lo que permite realizar 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 ordenación ni campos clave (no hay garantía de que el archivo esté organizado en campo clave o campo de clave principal). Una entrada de índice por cada tupla del 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.

Esta sección está vacía. Puedes ayudarnos agregándole algo. ( Abril 2023 )

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 balanceados , árboles B+ y hashes . ^[4]

En Microsoft SQL Server , el nodo hoja del índice agrupado corresponde a los datos reales, no simplemente a 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 de manera simultánea y, por lo tanto, necesitan 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 lograr una mejora sustancial del 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 necesarios. En otras palabras, el índice solo 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 propio índice contiene los campos de datos requeridos y puede responder a los datos requeridos.

Considere la siguiente tabla (se omiten otros campos):

Para encontrar el nombre de la 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 corresponden a una tabla específica. Las consultas que realizan operaciones de unión o acceden a varias tablas pueden considerar la posibilidad de incluir índices de cobertura en más de una de estas tablas. ^[7]

Un índice de cobertura puede acelerar considerablemente la recuperación de datos, pero puede ser en sí mismo grande debido a las claves adicionales, que ralentizan la inserción y actualización de datos. Para reducir el tamaño de este índice, algunos sistemas permiten incluir campos que no son clave en el índice. Los campos que no son clave en sí mismos no forman parte del ordenamiento del índice, sino que solo se incluyen en el 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 SQL de la ISO no cubre los aspectos físicos. Los índices son una de las partes físicas de la concepción de la base de datos, entre otras, como el almacenamiento (espacio de tablas o grupos de archivos). Todos los proveedores de RDBMS proporcionan una sintaxis con algunas opciones específicas que dependen de las capacidades de su software.CREATE INDEX

• Bloqueo de índice
• Índice invertido  – Tipo de índice de base de datos
• Indexación de motores de búsqueda  : método para la gestión de datos